二分法是一种基础的算法策略，通常又叫二分查找，一般用于查找一个有序数组中的某个值的位置或者给定的特定值的插入位置，复杂度为O($logN$)。一般而言，二分法的思路很简单，无非就是每次根据中值判断，然后缩减区间到原来的一半。

事实上，有序并不是使用二分的必要条件，只要能正确构建左右两侧的淘汰逻辑，就可以使用二分。关于这种情况，下面的例题中会有所提及。

例题一

在一个有序数组中（默认为从小到大排列），使用二分法查找某个数是否存在。如果存在则返回true，反之返回false。

代码实现如下：

package com.test;

import java.util.Arrays;

public class BinarySearch {
    public static boolean exist(int[] sortedArray, int num) {
        if(sortedArray == null || sortedArray.length == 0){
            return false;
        }
        int L = 0;
        int R = sortedArray.length - 1;
        int mid = 0;
        while(L < R){
            mid = L + ((R - L) >> 1);
            if(sortedArray[mid] == num){
                return true;
            }
            else if(sortedArray[mid] > num){
                R = mid - 1;
            }
            else{
                L = mid + 1;
            }
        }
        return sortedArray[L] == num;
    }
    // for test
    public static boolean comparator(int[] sortedArray, int num){
        for(int item: sortedArray){
            if(item == num){
                return true;
            }
        }
        return false;
    }
    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int)(maxSize * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue * Math.random()) - (int)(maxValue * Math.random()));
        }
        return arr;
    }
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 10;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            Arrays.sort(arr);
            int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
            if (comparator(arr, value) != exist(arr, value)) {
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Accessed!" : "Error!");
    }
}

上述代码使用了前一篇文章所介绍的对数器来验证二分的方法 exist() 写得是否正确。还要多说一句的是关于以上代码的第14行，大家习惯的写法似乎是 mid = (L + R) / 2 。事实上，这种写法是存在整数溢出的风险的，因为 L + R 的结果可能会超出 int 数据类型的表示范围。除了上述代码中的写法，L / 2 + R / 2 也是可以的。

例题二

在一个有序数组中（默认为从小到大排列），使用二分法找到大于等于某个数最左侧的位置并返回。

代码实现如下：

package com.test;

import java.util.Arrays;

public class BSNearLeft {
    public static int nearestIndex(int[] sortedArray, int num){
        int L = 0;
        int R = sortedArray.length - 1;
        int index = -1;
        while(L <= R){
            int mid = L + ((R - L) >> 1);
            if(sortedArray[mid] >= num){
                index = mid;
                R = mid - 1;
            }
            else{
                L = mid + 1;
            }
        }
        return index;
    }
    // for test
    public static int comparator(int[] sortedArray, int num){
        for(int i = 0; i < sortedArray.length; i++){
            if(sortedArray[i] >= num){
                return i;
            }
        }
        return -1;
    }
    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue){
        int[] arr = new int[(int)(maxSize * Math.random())];
        for(int i = 0; i < arr.length; i++){
            arr[i] = (int)((maxValue + 1) * Math.random()) - (int)(maxValue * Math.random());
        }
        return arr;
    }

    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 10;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            Arrays.sort(arr);
            int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
            if (comparator(arr, value) != nearestIndex(arr, value)) {
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Accessed!" : "Error!");
    }
}

例题三

在一个有序数组中（默认为从小到大排列），使用二分法找到小于等于某个数最右侧的位置并返回。

代码实现如下：

package com.test;

import java.util.Arrays;

public class BSNearLeft {
    public static int nearestIndex(int[] sortedArray, int num){
        int L = 0;
        int R = sortedArray.length - 1;
        int index = -1;
        while(L <= R){
            int mid = L + ((R - L) >> 1);
            if(sortedArray[mid] <= num){
                index = mid;
                L = mid + 1;
            }
            else{
                R = mid - 1;
            }
        }
        return index;
    }
    // for test
    public static int comparator(int[] sortedArray, int num){
        for(int i = sortedArray.length - 1; i >= 0; i--){
            if(sortedArray[i] <= num){
                return i;
            }
        }
        return -1;
    }
    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue){
        int[] arr = new int[(int)(maxSize * Math.random())];
        for(int i = 0; i < arr.length; i++){
            arr[i] = (int)((maxValue * Math.random()) - (int)(maxValue * Math.random()));
        }
        return arr;
    }

    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 10;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            Arrays.sort(arr);
            int value = (int) (maxValue * Math.random()) - (int) (maxValue * Math.random());
            if (comparator(arr, value) != nearestIndex(arr, value)) {
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Accessed!" : "Error!");
    }
}

例题四

在一个无序数组中，任意两个相邻的元素不相等，返回任意一个局部最小值的位置。

代码实现如下：

package com.test;

public class LocalMinimum {
    public static int localMinimum(int[] arr){
        if(arr.length == 0 || arr == null){
            return -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 L = 1;
        int R = arr.length - 2;
        while(L < R){
            int mid = (L + R) / 2;
            if(arr[mid] > arr[mid + 1]){
                L = mid + 1;
            }
            else if(arr[mid] > arr[mid - 1]){
                R = mid - 1;
            }
            else{
                return mid;
            }
        }
        return L;
    }
    // for test
    public static boolean isRight(int[] arr, int index){
        if(arr.length <= 1){
            return true;
        }
        if(index == 0){
            return arr[0] < arr[1];
        }
        if(index == arr.length - 1){
            return arr[arr.length - 1] < arr[arr.length - 2];
        }
        return arr[index] < arr[index - 1] && arr[index] < arr[index + 1];
    }
    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue){
        int[] arr = new int[(int)(maxSize * Math.random())];
        if(arr.length > 0){
            arr[0] = (int)(maxValue * Math.random()) - (int)(maxValue * Math.random());
        }
        for(int i = 1; i < arr.length; i++){
            do{
                arr[i] = (int)(maxValue * Math.random()) - (int)(maxValue * Math.random());
            }while(arr[i] == arr[i - 1]);
        }
        return arr;
    }

    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 30;
        int maxValue = 100;
        boolean flag = true;
        for(int i = 0; i < testTime; i++){
            int[] arr = generateRandomArray(maxSize, maxValue);
            if(!isRight(arr, localMinimum(arr))){
                flag = false;
                break;
            }
        }
        if(!flag){
            System.out.println("Error!");
        }
        else{
            System.out.println("Accessed!");
        }
    }
}