Here is small snippet to find minimum element in rotated sorted array. The code uses a modified binary search to search the element from the array.
package search; public class RotatedArray { static int arr[] ={7,8,9,10,11,13,24,1,2,3,4,5,6}; public static int search(int low, int high){ if(low>high) return -1; if(arr[low]>arr[high]){ int mid = (low+high)/2; if(arr[mid]>arr[high]) return search(mid+1,high); else return search(low,mid); } return low; } public static void main(String[] args) { int min = RotatedArray.search(0,arr.length-1); System.out.println(min); } }
BUG:
int mid = (low+high)/2;
It doesn’t seems to be; But it is;
Lets assume low and high value is Integer.MAX_VALUE;
output will come as -1; which is not correct There this line should be change
int mid = low + (high – low)/2