查找第一个等于目标值的位置时，需在找到目标后继续向左搜索。当arr[mid]==target时，记录位置并令r=mid-1；当arr[mid]target时，r=mid-1，最终返回最早出现的索引或-1。
二分查找是一种在有序数组中快速定位目标值的经典算法，时间复杂度为 O(log n)。但在实际开发中，我们常常遇到一些变体问题，比如查找第一个等于目标值的位置、最后一个等于目标值的位置，或者查找插入位置等。这些场景下标准的二分查找需要进行适当调整。
查找第一个等于目标值的位置
当数组中存在重复元素时，我们可能希望找到目标值第一次出现的索引。
关键在于：即使找到了目标值，也不能立即返回，而是要继续向左搜索。
- 当 arr[mid] == target 时，记录当前位置，并将右边界 r = mid - 1，继续查找左边是否还有更早的匹配项。
- 当 arr[mid] ，说明目标在右半部分，l = mid + 1。
- 当 arr[mid] > target，说明目标在左半部分，r = mid - 1。
示例代码：
立即学习“Java免费学习笔记（深入）”；
function findFirstPosition(arr, target) {
let l = 0, r = arr.length - 1;
let result = -1;
while (l <= r) {
const mid = Math.floor((l + r) / 2);
if (arr[mid] === target) {
result = mid;
r = mid - 1; // 继续向左找
} else if (arr[mid] < target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return result;
}
查找最后一个等于目标值的位置
与上一种情况相反，我们要找的是目标值最后一次出现的位置。
核心思路是：即使找到目标值，也要继续向右搜索。
- 当 arr[mid] == target 时，更新结果并让 l = mid + 1。
- 其余条件与标准二分一致。
示例代码：
立即学习“Java免费学习笔记（深入）”；
function findLastPosition(arr, target) {
let l = 0, r = arr.length - 1;
let result = -1;
while (l <= r) {
const mid = Math.floor((l + r) / 2);
if (arr[mid] === target) {
result = mid;
l = mid + 1; // 继续向右找
} else if (arr[mid] < target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return result;
}
查找插入位置（lower bound）
适用于确定目标值应插入的位置，以保持数组有序。如果目标值已存在，插入位置为其首次出现的位置前。
这在实现有序集合或去重插入时非常有用。
不需要判断是否完全相等，只需找到第一个大于等于目标值的位置。
示例代码：
立即学习“Java免费学习笔记（深入）”；
function findInsertPosition(arr, target) {
let l = 0, r = arr.length - 1;
let result = arr.length; // 默认插在末尾
while (l <= r) {
const mid = Math.floor((l + r) / 2);
if (arr[mid] >= target) {
result = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return result;
}
查找大于目标值的最小元素
有时我们需要找出第一个严格大于目标值的元素，例如在范围查询或自动补全中。
可以基于二分变形实现。
示例代码：
立即学习“Java免费学习笔记（深入）”；
function findFirstGreaterThan(arr, target) {
let l = 0, r = arr.length - 1;
let result = -1;
while (l <= r) {
const mid = Math.floor((l + r) / 2);
if (arr[mid] > target) {
result = arr[mid];
r = mid - 1;
} else {
l = mid + 1;
}
}
return result;
}
基本上就这些常见变体。掌握它们的关键是理解二分的本质：通过比较缩小搜索空间。根据具体需求调整边界移动逻辑即可。不复杂但容易忽略细节。
