二分查找是什么？二分查找的边界条件

星降

发布时间：2025-08-21 14:24:01

250人浏览过

来源于php中文网

原创

二分查找的边界处理需明确搜索区间为左闭右闭[left, right]或左闭右开[left, right)，前者while条件为left

二分查找是什么？二分查找的边界条件

二分查找是一种高效的搜索算法，它通过不断将搜索区间减半来快速定位目标值。关键在于确定正确的边界条件，以避免无限循环或错过目标值。

二分查找的核心在于理解和正确处理边界条件。

如何理解二分查找的边界？

二分查找的边界问题，说白了，就是确定

left

和

right

指针的移动策略。不同的边界处理方式会直接影响到算法的正确性，尤其是在处理一些边界情况，例如目标值不存在，或者目标值位于数组的边缘时。

解决方案：

明确搜索区间： 始终明确
```
left
```
和
```
right
```
指针定义的搜索区间是左闭右闭
```
[left, right]
```
还是左闭右开
```
[left, right)
```
。这直接决定了
```
while
```
循环的条件以及
```
left
```
和
```
right
```
指针的更新方式。
```
while
```
循环条件：
- 左闭右闭
  [left, right]
  ：
```
while (left <= right)
```
  。循环继续的条件是
```
left
```
  指针小于等于
```
right
```
  指针，意味着当
```
left
```
  和
```
right
```
  指针指向同一个元素时，仍然需要进行比较。
- 左闭右开
  [left, right)
  ：
```
while (left < right)
```
  。循环继续的条件是
```
left
```
  指针小于
```
right
```
  指针，意味着当
```
left
```
  和
```
right
```
  指针指向同一个位置时，循环结束。
```
left
```
和
right
指针的更新：
- 左闭右闭
  [left, right]
  ：
  - ```
  nums[mid] < target
```
  ：
```
  left = mid + 1;
```
  因为
```
  nums[mid]
```
  已经小于
```
  target
```
  ，所以下一个搜索区间不包含
```
  mid
```
  ，因此
```
  left
```
  更新为
```
  mid + 1
```
  。
- ```
nums[mid] > target
```
    ：
```
right = mid - 1;
```
    因为
```
nums[mid]
```
    已经大于
```
target
```
    ，所以下一个搜索区间不包含
```
mid
```
    ，因此
```
right
```
    更新为
```
mid - 1
```
    。
- 左闭右开
  [left, right)
  ：
  - ```
  nums[mid] < target
```
  ：
```
  left = mid + 1;
```
  与左闭右闭相同。
- ```
nums[mid] > target
```
    ：
```
right = mid;
```
    因为
```
nums[mid]
```
    已经大于
```
target
```
    ，而搜索区间不包含
```
right
```
    ，所以
```
right
```
    直接更新为
```
mid
```
    。
处理目标值不存在的情况： 在循环结束后，需要判断目标值是否存在。
- 左闭右闭
  [left, right]
  ：如果
```
left > right
```
  ，说明目标值不存在。
- 左闭右开
  [left, right)
  ：如果
```
left == right
```
  ，说明目标值不存在。
代码示例 (左闭右闭)：

public int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // 防止溢出
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 目标值不存在
}

代码示例 (左闭右开)：

public int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length; // 注意：right 初始化为 nums.length

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return -1; // 目标值不存在
}

二分查找的常见变体有哪些？

二分查找不仅仅是查找一个确切的值，它还可以用于解决许多变体问题，例如：

基于慧博CMS修改的购物网站系统

基于慧博CMS商城系统的修改，部分BUG已修正，并优化了页面和字体，新添加产品导航，方便客户查找自己想要的产品，本系统为永久免费系统，界面为绿色，如果你想修改成其他颜色，请自己参照代码进行修改，谢谢。后台地址：你的网站地址/admin支持文件夹和二级域名用户名和密码admin

下载

查找第一个等于目标值的元素： 当数组中存在重复元素时，找到第一次出现目标值的索引。
查找最后一个等于目标值的元素： 类似地，找到最后一次出现目标值的索引。
查找第一个大于等于目标值的元素： 找到数组中第一个大于或等于目标值的元素的索引。
查找最后一个小于等于目标值的元素： 找到数组中最后一个小于或等于目标值的元素的索引。

这些变体问题的关键在于，在找到目标值后，不要立即返回，而是继续缩小搜索范围，直到找到满足特定条件的元素。例如，要查找第一个等于目标值的元素，当

nums[mid] == target

时，需要将

right

指针向左移动，继续在左半部分查找。

如何在非排序数组中使用二分查找的思想？

虽然二分查找本身要求数组必须是有序的，但其“分而治之”的思想可以应用于非排序数组中的某些问题，例如：

快速选择算法： 用于在无序数组中查找第 k 个最小（或最大）的元素。其核心思想是使用类似于快速排序的分区操作，每次将数组划分为两部分，并根据目标元素的位置选择继续在哪一部分进行搜索。
寻找峰值： 在无序数组中寻找峰值元素（大于其相邻元素的元素）。可以使用类似二分查找的方式，每次选择数组的中间元素，并根据其与相邻元素的大小关系，选择继续在哪一半进行搜索。

需要注意的是，这些算法虽然借鉴了二分查找的思想，但并不完全等同于二分查找，因为它们需要根据具体问题的特点进行调整和修改。

javascript作用域链是什么_它如何影响变量的查找？

JavaScript中的属性描述符是什么_如何控制对象属性

如何理解Javascript的执行上下文_执行上下文怎样影响Javascript代码运行？

JavaScript中如何操作数组_数组方法你全部掌握了吗

javascript原型链如何工作_它与类继承有何不同？