分享｜二分查找详解及其变种实现&LeetCode题解
bitkevin
2812
2021.09.11
2025.01.19
发布于 未知归属地
二分查找学习分享

二分查找(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行），当中间元素值等于目标数时：

如果为数组第一个元素，或者mid左侧的数不为目标数时则返回mid
否则 high=mid-1, 继续向左侧查找

  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) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == n-1) || (a[mid + 1] != value)) 
        return mid;
      else 
        low = mid + 1;
    }
  }
  return -1;
}

这个有序数组中有重复的元素，需要查找出最后一个等于目标值的元素。还是只用修改算法退出条件（11-14行），当中间元素值等于目标数时：

如果为数组最后一个元素，或者mid右侧的数不为目标数时则返回mid
否则 low=mid+1, 继续向右侧查找

  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) {
      if ((mid == 0) || (a[mid - 1] < value)) 
        return mid;
      else 
        high = mid -1;
    } else{
      low = mid + 1;
    }
  }
  return -1;
}

这个有序数组中有重复的元素，需要查找出第一个等于目标值的元素。相对于查找第一个等于元素的算法，修改算法结束条件，当中间元素值大于等于目标数时：

如果为数组第一个元素，或者mid左侧的数小于目标数时则返回mid
否则 high=mid-1, 继续向左侧查找

  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) {
      if ((mid == n-1) || (a[mid + 1] > value)) 
        return mid;
      else 
        low = mid + 1;
    } else{
      high = mid - 1;
    }
  }
  return -1;
}
    这个有序数组中有重复的元素，需要查找出第一个等于目标值的元素。相对于查找最后一个等于元素的算法，修改算法结束条件，当中间元素值小于等于目标数时：

如果为数组最后一个元素，或者mid右侧的数大于目标数时则返回mid
否则 low=mid+1, 继续向右侧查找

  1. LeetCode 33题 旋转排序数组的二分查找
    整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

    这道题看似查找，其实还是二分查找的变种。由于数组中元素不重复，命中时直接返回索引，不命中时可以把数组按中间索引切分成两个区间 [low,mid)和(mid,high]。由循环数组的定义可知，这两个区间总有一个是有序的。

    如果[low,mid)有序且目标数落在这个区间，就在这个区间二分查找，否则就在(mid,high]中二分查找。反之如果(mid,high]区间有序且目标数落在这个区间，就在这个区间二分查找，否则在[low,mid)区间二分查找。

   代码示例如下(c++实现)：
int binarySearch(vector<int>& nums, int target) {
	if(nums.empty())
		return -1;
	int low = 0;
	int high = nums.size()-1;
	while(low <= high){
		int mid = low+(high-low)/2;
		if(nums[mid] == target){
			return mid;
		}
		if(nums[low] <= nums[mid]){
			if(nums[low] <= target && target < nums[mid])
				high = mid-1;
			else
				low =  mid+1;
		}else{
			 if(nums[mid] < target && target <= nums[high])
				low = mid+1;
			else
				high =  mid-1;
		}
	}
	return -1;
}
  1. LeetCode 34题 在排序数组中查找元素的第一个和最后一个位置
    给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

   这道题是要在排序数组中同时查找得到目标数的下界和上界，由于二分查找只能朝一个方向查找，所以有需要两次二分查找：先查找到下界，再从下界开始查找上界。代码实现如下：

    vector<int> searchRange(vector<int>& nums, int target) {
        int low = 0;
        int high = nums.size()-1;
        vector<int> res{-1,-1};
        while(low <= high) {
            int mid = low+(high-low)/2;
            if(nums[mid] < target){
                low = mid + 1;
            }else if(nums[mid] > target){
                high = mid - 1;
            }else{
                if(mid == 0 || nums[mid-1] != target){
                    res[0] = mid;
                    break;
                }
                high = mid - 1;
            }
        }
        if(res[0] < 0)
            return res;
        low = res[0];
        high = nums.size()-1;
        while(low <= high) {
            int mid = low+(high-low)/2;
            if(nums[mid] < target){
                low = mid + 1;
            }else if(nums[mid] > target){
                high = mid - 1;
            }else{
                if(mid == nums.size()-1 || nums[mid+1] != target) {
                    res[1] = mid;
                    break;
                }
                low = mid + 1;
            }
        }
 
        return res;
    }
  1. 二分查找的缺点
    看过了二分查找实现之后，我们可以发现二分查找有以下局限性：

依赖数组实现，需要使用数组连续存储数据
针对的是有序数据，必须是有序的数才能使用
数据量太大太小都不适合，数据太大内存没有足够连续内存，数据太小体现不出性能优势

  1. 二分查找的优势
    通过学习以上二分查找的变体，我们发现二分查找很适合区间查找，而且时间复杂度都为O(logn)。实际上在工程上一般的查找场景都是使用二叉搜索树(例如红黑树)或者哈希表来实现的，二分查找的优势在于对有序数组的区间查找，二叉搜索树和哈希表区间查找不方便。

    此外我们知道二分查找依赖于数组实现，链表要实现二分查找，可以使用跳跃表(Skip List)来实现，redis中正是使用跳表实现了键值的高效区间查找。

————————————————
欢迎访问我的博客
https://blog.csdn.net/bitkevin/article/details/119812156

评论 (5)