Find the minimum element in the rotated sorted sorted array

Question : Find the minimum element in the rotated sorted array.
So for example we have sorted array as -

2,3,6,12, 15, 18.

Now suppose the array is rotated k times ( we don’t know k), such that array becomes

15, 18,2,3,6,12

Answer - The answer to this lies on the fact that if we can find the point on inflection and things will be simple. So if we can have 2 sub arrays A and B,

  
// always restrict the search to the unsorted   
// sub-array. The min is always there.  
public static int findMin(int\[\] a, int start, int end){  
  int mid = (start + end)/2;  
  if(start == mid){//only 1 element  
    return a\[mid+1\];  
  }else if(a\[start\] > a\[mid\]){  
    return findMin(a, start, mid);  
  }else if(a\[mid+1\] > a\[start\]){  
    return findMin(a, mid+1, end);  
  }  
  //else{  
  //  return a\[mid+1\];  
  //}  
}

To begin with we call findMin(array, 0, array.length-1).
Doing it iteratively:

  
// index of first element  
l = 0  
  
// index of last element.  
h = arr.length - 1  
  
// always restrict the search to the unsorted   
// sub-array. The min is always there.  
while (arr\[l\] > arr\[h\]) {  
        // find mid.  
        mid = (l + h)/2  
        // decide which sub-array to continue with.  
        if (arr\[mid\] > arr\[h\]) {  
                l = mid + 1  
        } else {  
                h = mid  
        }  
}  
// answer  
return arr\[l\]

See also