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.
public class Solution { public int search(int[] A, int target) { // Start typing your Java solution below // DO NOT write main() function int left = 0; int right = A.length -1; while(left <= right){ int m = left + (right - left)/2; //same as (left+right) /2 inorder to aviod overflow if(A[m] == target) return m; if(A[m] >= A[left]){//bottom part is sorted if(A[left] <= target && target< A[m]){// wrong here right = m - 1; } else{ left = m + 1; } } if(A[m] <= A[right])//upper part is sorted { if(A[m] < target && target <= A[right]){//wrong here left = m +1; } else{ right = m -1; } } } return -1; } }
mistakes: boundary cases
learned: when search in sorted array, if mid in sorted left search left,else go right