Question : Find the minimum element in the rotated sorted array.
So for example we have sorted array as -
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,
To begin with we call
Doing it iteratively:
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]
def findMin(arr):
ReplyDeleteprint("Finding min in a rotated sorted array of integers")
low = 0
high = len(arr) - 1
while low < high:
mid = int((low + high)/2)
left = mid - 1
right = high
if arr[mid] > arr[left] and arr[mid] > arr[right]:
low = mid
elif arr[mid] > arr[left] and arr[mid] < arr[right]:
high = mid
else:
return arr[mid]