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

<p>二分查找的边界处理需明确搜索区间为左闭右闭[left, right]或左闭右开[left, right)，前者while条件为left <= right，更新right = mid - 1；后者while条件为left < right，更新right = mid；两种方式均需在循环后判断目标是否存在。常见变体包括查找首个/末个等于目标值的元素、首个大于等于或最后一个小于等于目标值的元素，关键是在命中目标后不立即返回，而是继续收缩边界。尽管二分查找要求有序数组，但其分治思想可应用于非排序数组的快速选择和峰值查找等问题，通过调整策略实现高效搜索。</p>

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

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

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

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

left

right

解决方案：

1. 明确搜索区间： 始终明确

   left

   和

   right

   指针定义的搜索区间是左闭右闭

   [left, right]

   还是左闭右开

   [left, right)

   。这直接决定了

   while

   循环的条件以及

   left

   和

   right

   指针的更新方式。

2. while

   循环条件：
   • 左闭右闭

     [left, right]

     ：

     while (left <= right)

     。 循环继续的条件是

     left

     指针小于等于

     right

     指针，意味着当

     left

     和

     right

     指针指向同一个元素时，仍然需要进行比较。
   • 左闭右开

     [left, right)

     ：

     while (left < right)

     。 循环继续的条件是

     left

     指针小于

     right

     指针，意味着当

     left

     和

     right

     指针指向同一个位置时，循环结束。

3. 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

       。

4. 处理目标值不存在的情况： 在循环结束后，需要判断目标值是否存在。

   • 左闭右闭

     [left, right]

     ： 如果

     left > right

     ，说明目标值不存在。
   • 左闭右开

     [left, right)

     ： 如果

     left == right

     ，说明目标值不存在。

5. 代码示例 (左闭右闭)：

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; // 目标值不存在
}

6. 代码示例 (左闭右开)：

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; // 目标值不存在
}

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

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

ImgGood

免费在线AI照片编辑器

下载

1. 查找第一个等于目标值的元素： 当数组中存在重复元素时，找到第一次出现目标值的索引。

2. 查找最后一个等于目标值的元素： 类似地，找到最后一次出现目标值的索引。

3. 查找第一个大于等于目标值的元素： 找到数组中第一个大于或等于目标值的元素的索引。

4. 查找最后一个小于等于目标值的元素： 找到数组中最后一个小于或等于目标值的元素的索引。

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

nums[mid] == target

right

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

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

1. 快速选择算法： 用于在无序数组中查找第 k 个最小（或最大）的元素。其核心思想是使用类似于快速排序的分区操作，每次将数组划分为两部分，并根据目标元素的位置选择继续在哪一部分进行搜索。

2. 寻找峰值： 在无序数组中寻找峰值元素（大于其相邻元素的元素）。可以使用类似二分查找的方式，每次选择数组的中间元素，并根据其与相邻元素的大小关系，选择继续在哪一半进行搜索。

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