二分查找学习总结
2021-09-19 / ryanxw

本文总结二分查找算法，其实该算法的思想是很简单的。即在有序的线性存储结构中进行查找。

  1. 选择mid位置的元素x是否等于target，相等则终止查找；
  2. 若x < target则需要向右半区间查找，更新左边界；
  3. 若x > target则需要向左半区间查找，更新右边界;
  4. 重复前面几步直到不能再划分为止。

1. 关键点：查询的边界确定问题

循环不变量的确定：即每次查询的左右区间维持一致，确保查询不重不漏

2. 代码

  • 左闭右闭写法 [left, right] 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int BinarySearch(int arr[], int len, int target){
        int left = 0;
        int right = len - 1;    // key：决定了[l, r]查找
        int mid = 0;
        while (left <= right){
            mid = left + (right - left) / 2;
            if (arr[mid] == target){
                return mid;
            }
            else if (arr[mid] < target){ // 需要更新左边界
                left = mid + 1;
            }
            else if (arr[mid] > target){ // 需要更新右边界
                right = mid - 1;
            }
        }
        return -1;
    }
  • 左闭右开写法 [left, right) 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int BinarySearch(int arr[], int len, int target){
        int left = 0;
        int right = len;    // key：决定了[l, r)查找
        int mid = 0;
        while (left < right){
            mid = left + (right - left) / 2;
            if (arr[mid] == target){
                return mid;
            }
            else if (arr[mid] < target){
                l = mid + 1;
            }
            else if (arr[mid] > target){
                r = mid;
            }
        }
        return -1;
    }