在數(shù)據(jù)結(jié)構(gòu)書籍中，在介紹二分法時，常常會加上有序這個前提條件，其中有序的定義要麼是從大到小排序，要麼是從小到大排序。

那么，有序真的是所有問題求解時使用二分的必要條件嗎？
答案是：不

只要正確構(gòu)建左右兩側(cè)的淘汰邏輯，你就可以使用二分法，那我們現(xiàn)在通過以下例子來了解二分法。

1、在一個有序數(shù)組中，找某個數(shù)是否存在
2、在一個有序數(shù)組中，找>=某個數(shù)最左側(cè)的位置
3、在一個有序數(shù)組中，找<=某個數(shù)最右側(cè)的位置
4、局部最小值問題

在一個有序數(shù)組中，找某個數(shù)是否存在

public static boolean exist(int[] sortedArr, int num) {
        if (sortedArr == null || sortedArr.length == 0) {
            return false;
        }
        int L = 0;
        int R = sortedArr.length - 1;
        int mid = 0;
        // L..R 至少兩個數(shù)的時候
        while (L < R) { 
            mid = L + ((R - L) >> 1);
            if (sortedArr[mid] == num) {
                return true;
            } else if (sortedArr[mid] > num) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return sortedArr[L] == num;
    }

在一個有序數(shù)組中，找某個數(shù)是否存在.png

在一個有序數(shù)組中，找大于等于某個數(shù)最左側(cè)的位置

public static int nearestIndex(int[] arr, int value) {
        int L = 0;
        int R = arr.length - 1;
        int index = -1; // 記錄最左的對號
        while (L <= R) { // 至少一個數(shù)的時候
            int mid = L + ((R - L) >> 1);
            if (arr[mid] >= value) {
                index = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return index;
    }

在一個有序數(shù)組中，找大于等于某個數(shù)最左側(cè)的位置 .png

在一個有序數(shù)組中，找小于等于某個數(shù)最右側(cè)的位置

public static int nearestIndex(int[] arr, int value) {
        int L = 0;
        int R = arr.length - 1;
        int index = -1; // 記錄最右的對號
        while (L <= R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] <= value) {
                index = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return index;
    }

在一個有序數(shù)組中，找小于等于某個數(shù)最右側(cè)的位置 .png

局部最小值問題

public static int getLessIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1; // no exist
        }
        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) / 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;
    }

局部最小可以使用二分法完成，定義局部最小時隱含的規(guī)律即：一個不存在相同元素的數(shù)組一定存在局部最小值，因為只需要找到一個局部最小值，這樣就可以使用二分查找將數(shù)組規(guī)模逐漸減小。
1、首先判斷數(shù)組第一個值是否小于右邊的值，若小于，則局部最小值為第一個數(shù)；否則進行下一步；
2、判斷數(shù)組的最后一個值是否小于左邊的值，若小于，則局部最小值為最后一個數(shù)；否則進行下一步；
3、通過二分法來驗證除首位和末尾位置的數(shù)組數(shù)據(jù)的局部最小值，若某值左右兩邊的值都大于該值，那么該值就屬于局部最小值；否則繼續(xù)通過二分法進行查找。