二分查找（binary search）是一种常见的查找算法，应用广泛，时间复杂度为 O(log n)。该算法采用了分治的思想，每次将查找区间缩小一半，从而大大提高查找效率。但是，在实际应用中，二分查找也会遇到一些特殊情况，需要特别考虑。本文将从多个角度分析二分查找的各种情况的算法实现。
一、基本二分查找
基本二分查找即为常规的二分查找算法，假设要在升序数组 nums 中查找目标值 target。
```
int binarySearch(vector
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
```
二、查找插入位置
有时候需要查找某个元素在有序数组中的插入位置。如果元素已经存在，返回它的下标；否则返回插入位置。
```
int binarySearch(vector
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
```
需要注意的是，如果 target 大于 nums 中的所有元素，left 将会超出 nums 的右边界。
三、查找第一个等于 target 的元素
在查找有序数组中第一个等于 target 的元素时，只需要在找到 target 的时候更新答案，然后继续在左半区间寻找可能有更小下标的 target。
```
int binarySearch(vector
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
if (mid == 0 || nums[mid - 1] < target) {
return mid;
} else {
right = mid - 1;
}
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
```
需要注意的是，如果 nums 中没有等于 target 的元素，结果为 -1。
四、查找最后一个等于 target 的元素
在查找有序数组中最后一个等于 target 的元素时，只需要在找到 target 的时候更新答案，然后继续在右半区间寻找可能有更大下标的 target。
```
int binarySearch(vector
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
if (mid == nums.size() - 1 || nums[mid + 1] > target) {
return mid;
} else {
left = mid + 1;
}
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
```
需要注意的是，如果 nums 中没有等于 target 的元素，结果为 -1。
五、查找第一个大于等于 target 的元素
在查找有序数组中第一个大于等于 target 的元素时，只需要在找到 target 的时候更新答案，然后继续在左半区间寻找可能有更小的大于等于 target 的元素。
```
int binarySearch(vector
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
if (mid == 0 || nums[mid - 1] < target) {
return mid;
} else {
right = mid - 1;
}
} else {
left = mid + 1;
}
}
return -1;
}
```
需要注意的是，如果 target 大于 nums 中的所有元素，结果为 nums 的大小。
六、查找最后一个小于等于 target 的元素
在查找有序数组中最后一个小于等于 target 的元素时，只需要在找到 target 的时候更新答案，然后继续在右半区间寻找可能有更大的小于等于 target 的元素。
```
int binarySearch(vector
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
if (mid == nums.size() - 1 || nums[mid + 1] > target) {
return mid;
} else {
left = mid + 1;
}
} else {
right = mid - 1;
}
}
return -1;
}
```
需要注意的是，如果 target 小于 nums 中的所有元素，结果为 -1。
二分查找的各种情况的算法实现主要有二分查找、查找插入位置、查找第一个等于 target 的元素、查找最后一个等于 target 的元素、查找第一个大于等于 target 的元素、查找最后一个小于等于 target 的元素。二分查找在实际应用中判断条件的不同，所采用的算法实现也会不同，需要根据具体情况选择相应实现。
微信扫一扫，领取最新备考资料
湖南希赛网络科技有限公司 版权所有 ©2001-2025 湘ICP备10203241号-14 湘公网安备43019002000749号
违法和不良信息举报 举报电话：18974879411 举报邮箱：wujunping@educity.cn
