Search in Rotated Sorted Array (Java+Python)

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

       

Search a item in sorted array we should think about binary search. Cause the given array has been rotated unknow times, so binary search can not be apply directly here.

       

Throgh observation we can see, no matter how a sorted array be rotated, there is

 always one side is sorted.

       

So we can pick the middle item at first and compare it with given array's leftMost and rightMost items to check which side is sorted, for given example 4, 5 , 6, 7 , 0 , 1, 2

mid is 7, leftMost is 4, rightMost is 2, because of 4<7 so we can know left side is sorted.

       

Depend on the conclusion we got above, if the given target is between 4->7, such as 6, we can just seach left side for it, otherwise we search the right side.

       

A trick situation is when duplicate exist in the array, discard the requriement of this quesiton, my         solution will also cover duplicate exist situation. 

If duplicate exist, then leftMost or rightMost item may equal to middle item, if only one of them equal to mid such as A[leftMost]==A[mid] then from leftMost to Mid should have same value. then we can only search the right side from mid to right most. If both A[rightMost] and A[leftMost] equal to A[Mid] we have to search both sides.

	"This question usually asked in an interview with two step ."
	"1, Assume the num in the array is unique"
	"2, if the num is not unique how to implement and how the complexity will going?"
	"for unique array, it is relative simple in logic, but don’t happy so earlier,"
	"this detail implementation is not easy to handle cause of the boundary case".
	"First, when looked a question about search an item in an sorted array, you first idea is apply binary search,"
	"for this question, our basic strategy is also binary search, but cause of this sorted array has been rotated,"
	"so We have to check it the num we are search is in specific range(left half or right half),"
	"because it is a sorted array before rotated,so there must a half be sorted although the array has been rotated,"
	"then we check if the num we are looing is possible in the sorted half, if it is, then search it, else,"
	"search another side."
	"the time complexity is O(lgn), because it is just a binary search with check the sorted range,"
	"the check sorted range can be did just by compare the start point and the mid point"
	public class Solution {
	public int search(int[] A, int target) {
	int begin=0;
	int end=A.length-1;
	return searchHelper(A, begin,end,target);
	}
	public int searchHelper(int[] A, int begin, int end, int target){
	if (begin>end) return -1;
	if (begin==end) {
	if (target==A[begin]){
	return begin;
	}
	else {
	return -1;
	}
	}
	int mid=(begin+end)/2;
	if (A[mid]==target) return mid;
	if(A[begin]<A[mid]){
	if (A[begin]<=target && target<A[mid]){
	return searchHelper(A,begin, mid, target);
	}
	else{
	return searchHelper(A, mid, end, target);
	}
	}
	else if (A[mid]<A[begin]){
	if (A[mid]<target && target<=A[end]){
	return searchHelper(A,mid,end, target );
	}
	else{
	return searchHelper(A, begin, mid, target);
	}
	}
	else{
	return searchHelper(A,mid+1, end, target);
	}
	}
	}
	"Then let's talk the the situation that if the array contain duplicate items"
	"In this situation, the only difference is the left point equal to mid point, under this situation , "
	"if mid point not equal to right, then we can just search the mid -> right range, or we have to search both side, "
	"example(2,2,4,6,8 and 2,2,2,4,7,8,2,2)"
	"because of the potential situation to search both side, so the time complexity is O(n) in worst case."
	public class Solution {
	public int search(int[] A, int target) {
	if(A==null ||A.length==0){
	return -1;
	}
	int st=0;
	int ed=A.length-1;
	return search(A, st, ed, target);
	}
	public int search(int[] A, int st, int ed, int target){
	if (st>ed){
	return -1;
	}
	int mid=st+(ed-st)/2;
	if (A[mid]==target){
	return mid;
	}
	if (A[st]<A[mid]){
	if (target>=A[st] && target<A[mid] ){
	return search(A, st, mid-1, target);
	}
	return search(A, mid+1, ed, target);
	}
	else if (A[st]>A[mid]){
	if (A[mid]<target && target<=A[ed]){
	return search(A, mid+1, ed, target);
	}
	return search(A, st, mid-1, target);
	}
	else{
	if (A[mid]!=A[ed]){
	return search(A, mid+1, ed, target);
	}
	else{
	int result=search(A, st, mid-1, target);
	if (result!=-1){
	return result;
	}
	return search(A, mid+1, ed, target);
	}
	}
	}
	}

view raw SearchInRotatedSortedArray.java hosted with ❤ by GitHub

	class Solution:
	# @param A, a list of integers
	# @param target, an integer to be searched
	# @return an integer
	def search(self, A, target):
	if A==None or len(A)==0:
	return -1;
	st=0;
	ed=len(A)-1
	return self.searchHelper(A, target, st, ed)
	def searchHelper(self, A, target, st, ed):
	if st>ed:
	return -1
	mid=(st+ed)/2
	if A[mid]==target:
	return mid
	if A[st]<A[mid]:
	if A[st]<=target<A[mid]:
	return self.searchHelper(A, target, st, mid-1)
	return self.searchHelper(A, target, mid+1, ed)
	elif A[st]>A[mid]:
	if A[mid]<target<=A[ed]:
	return self.searchHelper(A, target, mid+1, ed)
	return self.searchHelper(A, target, st, mid-1)
	else:
	if A[mid]!=A[ed]:
	return self.searchHelper(A, target, mid+1, ed)
	result=self.searchHelper(A, target, st, mid-1)
	if result!=-1:
	return result
	return self.searchHelper(A, target, mid+1, ed)

view raw SearchInRotatedSortedArray.py hosted with ❤ by GitHub