WZX's blog 海滩上捡贝壳的孩子

二分查找算法分析


搜索区间,终止条件和搜索策略三个方面分析二分查找算法,目标查找和上下边界的查找。

目标查找

查找一个目标数,返回其索引,若没有查找到,返回-1。若存在重复的目标数,则会随机返回一个目标数的索引。

int binary_search(const int arr[], int start, int end, int key) {
    int ret = -1;

    int mid = 0;
    while (start <= end) {
        // 防止溢出
        mid = start + (end - start) / 2;
        if (arr[mid] < key){
            start = mid + 1;
        }else if (arr[mid] > key){
            end = mid - 1;
        }else {
            ret = mid;  
            break;
        }
    }

    return ret;
}
  • 搜索区间:$[start,end]$ 闭区间
  • 搜索策略:二分查找每次查找都会使搜索区间缩小一半。因为序列是有序的,所以判断中间值与目标值的大小,就可以将搜索区间缩小为 $[start,middle-1]$ 或者 $[middle+1,end]$
  • 终止条件
    • 找到目标数arr[mid] == key
    • start > end,即搜索区间 $[start,end]$ 为空,出现这种情况说明序列中不存在目标数。而start == end时,仍存在不为空的搜索区间,所应该继续搜索

下界查找

查找一个目标数,返回其索引,若没有查找到,返回-1。若存在重复的目标数,则会返回最小的索引。

下面的两种写法的区别为搜索区间的不同,一种为 $[start,end]$,另一种为 $[start,end)$

写法一

int lower_bound(const int arr[], int start, int end, int key) {
    int ret = -1;
    int term = end;

    int mid = 0;
    while (start <= end) {
        mid = start + (end - start) / 2;
        if (arr[mid] < key){
            start = mid + 1;
        }else{
            end = mid - 1;
        }
    }

    if (start <= term && arr[start] == key){
        ret = start;
    }
    return ret;
}
  • 搜索区间:$[start,end]$ 闭区间,end参数应传入arr.size()-1
  • 搜索策略
    • arr[mid] < key时,搜索区间缩小为 $[middle+1,end]$ ,此时下界仍在搜索区间内
    • arr[mid] > key时,搜索区间缩小为 $[start,middle-1]$ ,此时下界仍在搜索区间内
    • arr[mid] == key时,搜索区间缩小为 $[start,middle-1]$ ,使搜索区间右侧向下界逼近
      • arr[mid]不是下界,自然被排除在区间之外
      • arr[mid]是下界,下界被排除在区间的右侧,但之后的迭代由于arr[mid] < key,搜索区间左侧会逼近下界,直至搜索空间变空
  • 终止条件
    • start > end,即搜索区间 $[start,end]$ 为空。由搜索策略可知,搜索区间的左侧和右侧都会向下界逼近,所以终止条件为搜索区间为空
    • 由区间搜索策略知,如果存在,下界为start。在目标数大于序列中的所有数时,需要考虑溢出的情况

写法二

int lower_bound(const int arr[], int start, int end, int key) {
    int ret = -1;
    int term = end - 1;

    int mid = 0;
    while (start < end) {
        mid = start + (end - start) / 2;
        if (arr[mid] < key){
            start = mid + 1;
        }else{
            end = mid;
        }
    }

    if (start <= term && arr[start] == key){
        ret = start;
    }
    return ret;
}
  • 搜索区间:$[start,end)$ 左闭右开,end参数应传入arr.size()
  • 搜索策略
    • arr[mid] < key时,搜索区间缩小为 $[middle+1,end)$ ,此时下界仍在搜索区间内
    • arr[mid] > key时,搜索区间缩小为 $[start,middle)$ ,此时下界仍在搜索区间内
    • arr[mid] == key时,搜索区间缩小为 $[start,middle)$ ,使搜索区间右侧向下界逼近
      • arr[mid]不是下界,自然被排除在区间之外
      • arr[mid]是下界,下界处于右侧开区间内,但之后的迭代由于arr[mid] < key,搜索区间左侧会逼近下界,直至搜索空间变空
  • 终止条件
    • start == end,即搜索区间 $[start,end)$ 为空。由搜索策略可知,如果存在,start为下界

上界查找

查找一个目标数,返回其索引,若没有查找到,返回-1。若存在重复的目标数,则会返回最大的索引。

下面的两种写法的区别为搜索区间的不同,一种为 $[start,end]$,另一种为 $[start,end)$

写法一

int upper_bound(const int arr[], int start, int end, int key) {
    int ret = -1;

    int mid = 0;
    while (start <= end) {
        mid = start + (end - start) / 2;
        if (arr[mid] > key){
            end = mid - 1;
        }else{
            start = mid + 1;
        }
    }

    if (end >= 0 && arr[end] == key){
        ret = end;
    }
    return ret;
}
  • 搜索区间:$[start,end]$ 闭区间
  • 搜索策略
    • arr[mid] < key时,搜索区间缩小为 $[middle+1,end]$ ,此时上界仍在搜索区间内
    • arr[mid] > key时,搜索区间缩小为 $[start,middle-1]$ ,此时上界仍在搜索区间内
    • arr[mid] == key时,搜索区间缩小为 $[middle+1,end]$ ,使搜索区间左侧向上界逼近
      • arr[mid]不是上界,自然被排除在区间之外
      • arr[mid]是上界,上界被排除在区间的左侧,但之后的迭代,搜索区间右侧会逼近上界,直至搜索空间变空
  • 终止条件
    • start > end,即搜索区间 $[start,end]$ 为空。由搜索策略可知,搜索区间的左侧和右侧都会向下界逼近,所以终止条件为搜索区间为空
    • 由区间搜索策略知,如果存在,上界为end。在目标数小于序列中的所有数时,需要考虑溢出的情况

写法二

int upper_bound(const int arr[], int start, int end, int key) {
    int ret = -1;

    int mid = 0;
    while (start < end) {
        mid = start + (end - start) / 2;
        if (arr[mid] > key){
            end = mid;
        }else{
            start = mid + 1;
        }
    }

    if (end >= 1 && arr[end-1] == key){
        ret = end - 1;
    }
    return ret;
}
  • 搜索区间:$[start,end)$ 左闭右开,end参数应传入arr.size()
  • 搜索策略
    • arr[mid] < key时,搜索区间缩小为 $[middle+1,end)$ ,此时上界仍在搜索区间内
    • arr[mid] > key时,搜索区间缩小为 $[start,middle)$ ,此时上界仍在搜索区间内
    • arr[mid] == key时,搜索区间缩小为 $[middle+1,end)$ ,使搜索区间左侧向上界逼近
      • arr[mid]不是上界,自然被排除在区间之外
      • arr[mid]是上界,上界排除在闭区间的左侧,但之后的迭代由于arr[mid] > key,搜索区间右侧会逼近上界,直至搜索空间变空
  • 终止条件
    • start == end,即搜索区间 $[start,end)$ 为空。由搜索策略可知,如果存在,end-1为下界

总结

  • 特别注意搜索空间的开闭
  • 在查找目标数时,可以在找到目标数时提前终止,其余的终止条件都为搜索空间为空
  • 下界查找时,找到目标数时,应该将搜索区间向下缩减
  • 上界查找时,找到目标数时,应该将搜索区间向上缩减
  • 上界查找时,搜索区间为开区间的情况下,结果需要减1
  • 上下界查找时,需要判断返回值是否是目标数

LeetCode上的34. Find First and Last Position of Element in Sorted Array为二分搜索的上下界查找的典型应用,完整答案可以查看题解

REFERENCE

[1] 二分查找详解
[2] 34. Find First and Last Position of Element in Sorted Array Solution


上一篇 YARN原理解析

下一篇 Hive原理解析

Comments

Content