Local Minimum of an array

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].

数组的局部最小值: 定义局部最小的概念。arr长度为1时，arr[0]是局部最小。arr的长度为N(N>1)时，如果arr[0]<arr[1]，那么arr[0]是局部最小；如果arr[N-1]<arr[N-2]，那么arr[N-1]是局部最小；如果0<i<N-1，既有arr[i]<arr[i-1]又有arr[i]<arr[i+1]，那么arr[i]是局部最小。

给定无序数组arr，已知arr中任意两个相邻的数都不相等，写一个函数，只需返回arr中任意一个局部最小出现的位置即可。

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]);
    }

}

From 牛客网

此题的关键在于根据中间元素的大小对数组进行二分 解法的时间复杂度为 O(log n)

public static int findLocalMinimum(int[] arr) {
        if ( arr.length == 0 )
            return -1;

            // Size 为 1 直接 return, 不会执行第二个判断
        else if ( arr.length == 1 || arr[0] < arr[1] )
            return 0;

        if ( arr[arr.length - 1] < arr[arr.length - 2] )
            return arr.length - 1;

        int left = 1;
        int right = arr.length - 2;
        int mid = 0;

        while ( left < right ) {
            mid = (left + right ) >> 1;
            if ( arr[mid] > arr[mid - 1] ) {
                right = mid - 1;
            } else if ( arr[mid] > arr[mid + 1] ) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
}