返回数组中的局部最小

返回数组中的局部最小

局部最小的定义：

所谓局部最小就是比它右边小同时也要比它左边小,如果是数组的第一个元素那么只需要比它下一个元素小也就是局部最小,如果是最后一个元素那么只需要比它上一个元素小就是局部最小,如果仅仅包含两个元素那么谁小谁就是局部最小。

注意：

这样的数组要整体无序且相邻数组元素不相等。

代码：

/**
 * 返回一个数组中的局部最小的数组元素的下标值
 * 所谓局部最小就是这个数组元素比它左边的小同时也比它右边的小
 * 注意：二分查找不一定非要数组有序
 */
public class JuBuMin {
    // arr 整体无序
    // arr 相邻的数不相等！
    public static int oneMinIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int N = arr.length;
        //如果数组就一个元素那这个元素就是局部最小
        if (N == 1) {
            return 0;
        }
        //边界情况就是如果第一个数组元素比它右边的数组元素小那么它就是局部最小
        if (arr[0] < arr[1]) {
            return 0;
        }
        /*
        下面可包含两种情况:
        1:边界情况就是数组元素最右边的值如果小于倒数第二个值那么它就是局部最小
        2:当数组元素有两个值的时候结合上面这个if也可以进行判断局部最小
         */
        if (arr[N - 1] < arr[N - 2]) {
            return N - 1;
        }
        int L = 0;
        int R = N - 1;
        // L...R 肯定有局部最小
        while (L < R - 1) {
            int mid = (L + R) / 2;
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                //如果既小于左边又小于右边的话那它就是局部最小
                return mid;
            } else {
                if (arr[mid] > arr[mid - 1]) {
                    //如果比它左边的值大那么就在左边继续找
                    R = mid - 1;
                } else {
                    //如果比它左边的值小那么就在右边继续找
                    L = mid + 1;
                }
            }
        }
        return arr[L] < arr[R] ? L : R;
    }