算法-二分查找及其应用

算法-二分查找及其应用

原理：

  • 在有序排列的数据下，目标值可以与当前数据的中间值比较，从而将查找范围去掉一半，因此，我们使用两个值定位这串数据的首尾

  • 如果数据恰好与中间值相等，则直接返回位置

  • 在左半部分则右侧指针指向中间索引 -1（减一是因为中间索引参与比较了因此向左来一位）

  • 右半部分同理

  • 如此反复，最终我们的中间索引会指向结果，并返回结果位置

  • 如果没有结果，则指针继续移动，会出现指针重叠，因此我们用此判断无结果，返回 -1

1
2
3
4
5
6
7
8
9
10
11
12

#二分查找——采用半开区间[i,j) 
public static int binarySearch(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 (target > a[m]) i = m + 1;
        else return m;
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12

#二分查找——采用闭区间[i,j]
public static int binarySearch(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;
}

基本的二分查找有以上两种方法，个人常用第一种方法。

接下来稍微变化一下二分查找，使其能够解决别的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#二分查找查找最左侧重复元素
#把中间索引移动到重复位置的最左侧，直到指向非目标数
public static int Leftmost(int[] a, int target) {
        int i = 0, j = a.length - 1, 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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#二分查找查找最右侧重复元素
#把中间索引移动到重复位置的最右侧，直到指向非目标数
public static int Rightmost(int[] a, int target) {
        int i = 0, j = a.length - 1, 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;
    }

以上两种可以进行简化

1
2
3
4
5
6
7
8
9
10
11
12

# 二分查找查找最左侧重复元素
# 返回值：返回的为大于等于目标最靠左侧的索引
public static int Leftmost2(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 i = m + 1;
    }
    return i;
}
1
2
3
4
5
6
7
8
9
10
11
12

# 二分查找查找最右侧重复元素
# 返回值：返回的为小于等于目标最靠右侧的索引，不一定需要查找到目标元素
public static int Rightmost2(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 i = m + 1;
    }
    return i - 1;
}

简单理解以上两个优化后函数的 if (target < a[m])的不同

  • 当需要查找最左侧元素时，如果中间值和目标值相等，我们需要把右侧边界向左推进 j = m - 1，因此无论target < 还是 = 中间值，我们都需要让 又边界向左推进

  • 当需要查找最右侧元素时，如果中间值和目标值相等，说明目标在右侧，因此我们左边界应当向右侧推进，i = m + 1

简单理解以上两个优化后函数的返回值不同

  • 如果我们进行简单的推算可以发现一个规律，当查找最左侧重复元素，最终 i 恰好落在重复的最左侧元素上，因此直接返回 i 值

  • 当进行最右侧查找，我们发现 i 在重复最右侧值的 +1 位置，因此我们需要减去 1

学习算法时的二分查找笔记，理解浅薄，见谅🙏🏻

code
#数据结构
算法-二分查找及其应用
https://www.zheep.top/2024/11/21/算法-二分查找及其应用/
作者
西行寺岩羊
发布于
2024年11月21日
许可协议