数据结构与算法——二分查找

二分查找

　　定义：二分查找（Binary Search）是一种在有序数组或列表中查找特定元素的搜索算法。该算法的基本思想是利用数组有序这一特性，通过不断将待搜索区间缩小一半来快速定位目标值。

左闭右闭

 public static int binarySearchBasic(int[] a, int target) {
        int i = 0, j = a.length - 1;    // 设置指针和初值
        // L 次  元素在最左边 L 次，  元素在最右边 2*L 次
        while (i <= j) {                // 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;
    }

问题1: 为什么是 i<=j 意味着区间内有未比较的元素, 而不是 i<j ?
   i==j 意味着 i,j 它们指向的元素也会参与比较
   i<j 只意味着 m 指向的元素参与比较
问题2: (i + j) / 2 有没有问题?
   当j为int类型最大值时，在首次循环中，i增大，j不变，因为二进制符号位的问题，m的值变为负数。因而通过右移一位解决问题，即?int m = (i + j) >>> 1。

左闭右开

public static int binarySearchAlternative(int[] a, int target) {
        int i = 0, j = a.length;     // 第一处
        while (i < j) {              // 第二处
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m;               // 第三处
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }

　　注意三处改动的地方；j索引在代码中为边界，所指元素不参与比较。

二分查找性能

　　时间复杂度

• 　　最坏情况：$O(\log n)$
• 　　最好情况：如果待查找元素恰好在数组中央，只需要循环一次 $O(1)$

　　空间复杂度

• 　　* 需要常数个指针 $i,j,m$，因此额外占用的空间是 $O(1)$?

深入了解二分查找

平衡版（最好情况与最坏情况时间复杂度一致）

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

Leftmost（返回最左侧重复元素）

public static int binarySearchLeftmost1(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;
}

Rightmost（返回最右侧重复元素）

public static int binarySearchRightmost1(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;
}

可以通过添加额外参数将两个函数合并为一个

public int findBoundary(int[] a, int t, boolean isLeft) {
    int i = 0;
    int j = a.length - 1;
    int candidate = -1;

    while (i <= j) {
        int m = (i + j) >>> 1;
        
        if (t < a[m]) {
            j = m - 1;
        } else if (t > a[m]) {
            i = m + 1;
        } else {
            candidate = m;
            if (isLeft) {
                j = m - 1; // 寻找左边界时，移动j到左边
            } else {
                i = m + 1; // 寻找右边界时，移动i到右边
            }
        }
    }

    return candidate;
}

?力扣题目

　　二分查找

　　搜索插入位置

　　在排序数组中查找元素的第一个和最后一个位置

来源?

　　b站：基础数据结构

　　路漫漫其修远兮，吾将上下而求索。