二分查找详解及其变种实现&LeetCode题解

最新推荐文章于 2022-07-19 11:41:06 发布

bitkevin

最新推荐文章于 2022-07-19 11:41:06 发布

阅读量432

点赞数 2

分类专栏：数据结构与算法文章标签：算法

本文链接：https://blog.csdn.net/bitkevin/article/details/119812156

版权

本文详细介绍了二分查找的基本原理和常见变体，包括查找目标值的下界、上界、大于等于目标值的元素以及小于等于目标值的元素。此外，还探讨了如何使用二分查找解决LeetCode的33题和34题，以及二分查找的优缺点。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

1.最基本的二分查找

2. 二分查找的下界查找第一个等于目标值的元素

3. 二分查找的上界查找最后一个等于目标值的元素

4. 查找第一个大于等于目标值的元素

5. 查找最后一个小于等于目标值的元素

6. LeetCode 33题旋转排序数组的二分查找

7. LeetCode 34题在排序数组中查找元素的第一个和最后一个位置

8. 二分查找的缺点

9. 二分查找的优势

二分查找(Binary Search)又叫折半查找，对于已排序的数组，是一种非常高效的排序算法，时间复杂度为O(logn)。二分查找很简单也很高效，但要写好用好二分查找却不容易，多数程序员都不能完整地实现一个无bug的二分查找。

1.最基本的二分查找

我们先来看一个最基本的二分查找，在一组无重复的数组中查找指定的数并返回数组索引。

int binarySearch(int* a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid = low + (high - low)/2;
    if (a[mid] == value) {
      return mid;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1;
}

容易错的地方：

循环结束条件

循环结束条件为 low <= high；

错误写法：low < high,low < high可能会导致死循环,边界判断很重要;

中间位置的计算

中间位置的计算可以写作 mid = (low+high)/2 或者 mid = low+(high-low)/2。但前者的问题是low和high比较大时low+high可能会溢出，超出int表达的最大范围。如果有对性能的极致要求，还可以把除2改为位运算，写作mid=low+((high-low)>>1)，位运算的性能要比除法好很多。

错误写法：面试中看到很多人写作 mid = (high-low)/2，这种写法肯定是错误的，只要low不是0,就会出错。

边界更新

中间值小于目标值时，low=mid+1；中间值大于目标值时，high=mid-1;

错误写法：low=mid; high=mid; 不但有重复计算，而且会导致死循环（例 low==high时）

注：此处的二分查找也可以通过递归实现，递归实现代码更加简洁，不过递归算法递归过深会有堆栈溢出的风险，面试中面试官也更愿意看到非递归的实现。

在实际应用中，很难保证数据不会有重复，而且我们可能需要查找满足条件的第一个或最后一个元素，下面看看二分查找的一些变体：

2. 二分查找的下界查找第一个等于目标值的元素

int binarySearch(int* a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + (high - low)/2;
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == 0) || (a[mid - 1] != value)) 
        return mid;
      else 
        high = mid - 1;
    }
  }
  return -1;
}

这个有序数组中有重复的元素，需要查找出第一个等于目标值的元素。相对第一个算法仅修改了算法退出条件（11-14行ÿ