# Find the minimum element in a sorted and rotated array

Take an example

int[] a = { 10, 11, 1, 2, 3, 4, 5, 6, 7, 8, 9, };

We can find the minimum element in O(logn), so first we divide the array in two parts in which one is sorted and other one is sorted, this process is continued until low is equal to high.

There are some differences and similarities with binary search algorithm.

private static int min(int a[]) {

int low = 0;

int high = a.length - 1;

while (low < high) {

int mid = (low + high) >>> 1;

if (a[mid] < a[high])

high = mid;

else

low = mid + 1;

}

return a[low];

}

int low = 0;

int high = a.length - 1;

while (low < high) {

int mid = (low + high) >>> 1;

if (a[mid] < a[high])

high = mid;

else

low = mid + 1;

}

return a[low];

}

## No comments:

## Post a Comment