神级算法——二分天下

二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高得查找方法。一般都是要求线性表有序，然后二分查找的时间复杂度为O(logN)。

不一样的二分

如果数组无序，难道就不能用二分查找了吗？答案是否定的，即使一个数组无序，也可以用二分查找来找。下面我就用两个例子来给你们上一课（膨胀了我，哈哈~~~）

例子1（旋转数组）：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

思路：

即使数组无序，但是我们还是可以使用二分查找来找出最小值。因为旋转数组部分有序，利用二分查找还是很容易查找到最小值

代码：

public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int low = 0 ; int high = array.length - 1;  
        while(low < high){
            int mid = low + (high - low) / 2;       
            if(array[mid] > array[high]){
                low = mid + 1;
            }else{
                high = mid;
            }  
        }
        return array[low];
    }
}

通过：

可能有人会觉得，即使无序可以使用二分查找，但是你这个旋转数组也是部分有序，所以可以使用二分查找。接下来我再讲解一道题来证明给你看——查找局部最小值。

例子2（查找局部最小值）

定义局部最小的概念。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中任意一个局部最小出现的位置即可。

思路：

先查找arr[0]和arr[N-1]，即第一个数和最后一个数是不是局部最小，如果是，直接返回这个数即可。
如果arr[0]>arr[1]，arr[N-1]>arr[N-2]，那么此时的情况就是这样的：

代码：

/**
 * @author god-jiang
 * @date 2020/1/11
 */
public class FindOneLessValueIndex {

    public static int getLessIndex(int[] arr) {
        //如果不存在直接return -1
        if (arr == null || arr.length == 0) {
            return -1;
        }
        //先看arr[0]和arr[N-1]是不是局部最小，是的话直接返回即可
        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 - left) / 2;
            if (arr[mid] > arr[mid - 1]) {
                right = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i != arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {6, 5, 3, 4, 6, 7, 8};
        printArray(arr);
        int index = getLessIndex(arr);
        System.out.println("index: " + index + ", value: " + arr[index]);

    }
}