## Thursday, December 29, 2011

### 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
}
}
return arr[l]
```

#### 1 comment:

1. def findMin(arr):
print("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]