二分查找

二分查找（Binary Search）是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。

这种搜索算法每一次比较都使搜索范围缩小一半，因此其时间复杂度是O(log n)，n是数组的元素数量。二分查找的效率远高于线性查找（时间复杂度为O(n)）。

然而，值得注意的是，二分查找要求数组必须是有序的，这是其能高效工作的前提。如果数组无序，则无法利用二分查找算法。此外，二分查找对于静态数据表（即不能改变数据表）尤其有用，对于动态数据表，则可能需要额外的数据结构来维护数据的有序性。

二分查找基本实现

// 二分查找基础
    public static int binarySearchBasic(int[] a, int target) {
        int i = 0, j = a.length - 1; // 设置指针和初值
        while (i <= j) {
            int m = (i + j) / 2;
            if(target < a[m]) { // 目标在左边
                j = m - 1;
            } else if (a[m] < target) { // 目标在右边
                i = m + 1;
            } else { // 找到了
                return m;
            }
        }
        return -1;
    }

对二分查找进行优化

 	// 二分查找基础 -- 优化
    // 如果二分查找数值过大, 可能会超过数据类型所表示的范围
    // 可以将(i + j) >>> 1 表示将(i+j)的值右移一位 == (i+j) / 2, 但是不会超数据类型所表示的范围
    
    public static int binarySearchBasic(int[] a, int target) {
        int i = 0, j = a.length - 1; // 设置指针和初值
        while (i <= j) {
            int m = (i + j) >>> 1;
            if(target < a[m]) { // 目标在左边
                j = m - 1;
            } else if (a[m] < target) { // 目标在右边
                i = m + 1;
            } else { // 找到了
                return m;
            }
        }
        return -1;
    }

对二分查找平衡优化

public static int binarySearchBalance(int[] a, int target) {
        int i = 0, j = a.length;
        while (i < j - i) {
            int m = (i+j) >>> 1;
            if(target < a[m]) {
                j = m;
            } else {
                i = m;
            }
        }
        if(a[i] == target) {
            return i;
        } else {
            return -1;
        }
    }

二分查找最左元素

public static int binarySearchLeftmost(int[] a, int target) {
        int i = 0, j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m -1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                // 记录候选位置
                candidate = m;
                j = m - 1;
            }
        }
        return candidate;
    }

二分查找最右元素

public static int binarySearchRightmost(int[] a, int target) {
        int i = 0, j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m -1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                // 记录候选位置
                candidate = m;
                i = m + 1;
            }
        }
        return candidate;
    }