Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Example
Input:
nums = [4,5,6,7,0,1,2], target = 0
Output:
4
Solution
we need to find the pivot element. This is where the pattern of ascending order is broken.
public class Solution {
public int Search(int[] A, int target) {
if(A.Length == 2)
{
if(A[0] == target) return 0;
if(A[1] == target) return 1;
}
int pivot = -1;
//return BinarySearch(A, 0, A.Length-1, target);
for(int i=0; i<A.Length-1; i++)
{
if (A[i] > A[i + 1])
{
pivot = i + 1 ; break;
}
}
if(pivot == -1)
return BinarySearch(A, 0, A.Length - 1, target);
else
{
if (target == A[pivot])
return pivot;
return BinarySearch(A, 0, pivot, target) == -1 ? BinarySearch(A, pivot, A.Length - 1, target): BinarySearch(A, 0, pivot, target);
}
}
public static int BinarySearch(int [] A, int left, int right, int target)
{
int mid = (left + right) / 2;
if (left > right)
return -1;
if (A[mid] == target)
return mid;
else if(A[left] <= A[mid]) //left is sorted properly
{
if (A[left] <= target && target <= A[mid])
return BinarySearch(A, left, mid, target);
else
return BinarySearch(A, mid + 1, right, target);
}
else if (A[mid] < A[left])
//right is sorted properly. eg 9,10,11,2,4,7,8 a(mid) = 2 is < aleft = 9 means left is wired and right is sorted
{
if (target > A[mid] && target < A[right])
return BinarySearch(A, mid, right, target);
else
return BinarySearch(A, left,mid-1, target);
}
else return -1;
}
}