**Problem**: Given an array ‘a’ of N distinct integers, design an O(log N) algorithm to find a local minimum: an index i such that a[i-1] > a[i] < a[i+1].

**Solution**: If a[0] < a[1] or a[N - 2] > a[N - 1] then a[0] or a[N - 1] is the local minimum, respectively. Pick a[mid] where mid = N / 2. If it's not the answer, we have three cases:

1) If a[mid - 1] < a[mid] < a[mid + 1], lower half will contain the local minimum.

2) If a[mid - 1] > a[mid] > a[mid + 1], upper half will contain the local minimum.

3) If a[mid - 1] < a[mid] > a[mid + 1], either half will contain the local minimum.

Search on the new interval recursively.

Explanation:

If a[1] < a[2], a[1] is an LM.

Otherwise, if a[n-1] > a[n], a[n] is an LM.

Otherwise, the array entries start out descending (going from a[1] to a[2]) and ends up ascending (going from a[n-1] to a[n]). It follows that an LM must exist somewhere in between. Examine a[n/2]. If a[n/2] > a[n/2+1], then by the same reasoning there is an LM in the upper half of the array. Similarly, if a[n/2] < a[n/2+1] there is an LM in the lower half of the array. Solve recursively in the appropriate half.

public class LocalMinimum {

public static int findLocalMinimum(int[] elements, int lowIndex, int highIndex) {

if (lowIndex > highIndex) {

return -1;

}

if (lowIndex == highIndex) {

return lowIndex;

}

if (lowIndex + 1 == highIndex) {

if (elements[lowIndex] < elements[highIndex]) {

return lowIndex;

}

return highIndex;

}

int midIndex = (lowIndex + highIndex) / 2;

if ((elements[midIndex] <= elements[midIndex - 1])

&& (elements[midIndex] <= elements[midIndex + 1])) {

return midIndex;

}

if (elements[midIndex] >= elements[midIndex + 1]) {

return findLocalMinimum(elements, midIndex, highIndex);

} else {

return findLocalMinimum(elements, lowIndex, midIndex);

}

}

public static void main(String[] args){

int Arr[] = {8,5,4,3,1,2,6,9};

int index = findLocalMinimum(Arr, 0, Arr.length-1);

System.out.println("local mimimum is "+Arr[index]);

}

}

## No comments:

Post a Comment