二分查找的边界处理需明确搜索区间为左闭右闭[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; // 目标值不存在}
二分查找的常见变体有哪些？
二分查找不仅仅是查找一个确切的值，它还可以用于解决许多变体问题，例如：
查找第一个等于目标值的元素： 当数组中存在重复元素时，找到第一次出现目标值的索引。
查找最后一个等于目标值的元素： 类似地，找到最后一次出现目标值的索引。
查找第一个大于等于目标值的元素： 找到数组中第一个大于或等于目标值的元素的索引。
查找最后一个小于等于目标值的元素： 找到数组中最后一个小于或等于目标值的元素的索引。
这些变体问题的关键在于，在找到目标值后，不要立即返回，而是继续缩小搜索范围，直到找到满足特定条件的元素。例如，要查找第一个等于目标值的元素，当
nums[mid] == target
时，需要将
right
指针向左移动，继续在左半部分查找。
如何在非排序数组中使用二分查找的思想？
虽然二分查找本身要求数组必须是有序的，但其“分而治之”的思想可以应用于非排序数组中的某些问题，例如：
快速选择算法： 用于在无序数组中查找第 k 个最小（或最大）的元素。其核心思想是使用类似于快速排序的分区操作，每次将数组划分为两部分，并根据目标元素的位置选择继续在哪一部分进行搜索。
寻找峰值： 在无序数组中寻找峰值元素（大于其相邻元素的元素）。可以使用类似二分查找的方式，每次选择数组的中间元素，并根据其与相邻元素的大小关系，选择继续在哪一半进行搜索。
需要注意的是，这些算法虽然借鉴了二分查找的思想，但并不完全等同于二分查找，因为它们需要根据具体问题的特点进行调整和修改。
以上就是二分查找是什么？二分查找的边界条件的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1516830.html
微信扫一扫 
支付宝扫一扫 
