二分查找的「左右为难」：如何优雅地找到数组中元素的首尾位置
当你在人群中寻找某个人时，你会怎么做？从头到尾挨个找？还是站在中间，问左边的人「他在你们那边吗」？聪明的你一定选择后者。今天我们就来聊聊二分查找中的一个经典问题——如何找到排序数组中目标元素的第一个和最后一个位置。
题目回顾
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums ，和一个目标值 target 。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target ，返回 [-1, -1] 。
关键要求：你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10],
target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10],
target = 6
输出：[-1,-1]
初学者的「暴力美学」
让我们先看看最直观的解法：
var searchRange = function(nums, target) {
let begin = -1, end = -1
for (var i = 0; i < nums.length; i++) {
if(begin === -1) {
if (nums[i] === target) {
begin = i
end = i
}
} else {
if (nums[i] === target) {
end = i
}
}
}
return [begin, end]
};
这个解法就像是在图书馆里从第一本书开始翻，直到找到你要的那本书的所有副本。虽然逻辑清晰，但是…
时间复杂度：O(n) 😱
面试官：「同学，你这是在逗我吗？题目明明要求 O(log n)！」
二分查找的「分身术」
既然要 O(log n)，那就必须祭出二分查找这个神器。但这里有个巧妙之处：我们需要找到 两个边界 ——左边界和右边界。
核心思想
找左边界 ：当找到目标值时，不要停下，继续向左搜索，看看还有没有更左的目标值
找右边界 ：当找到目标值时，不要停下，继续向右搜索，看看还有没有更右的目标值
这就像是在拥挤的地铁里找座位，找到一个空座位后，你还要看看旁边是不是还有连续的空座位。
正确的实现
var searchRange = function(nums, target) {
// 查找左边界（最左边的目标值）
const findLeft = (nums, target) => {
let left = 0, right = nums.length - 1, result = -1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
result = mid;
right = mid - 1;
// 关键：继续向左搜索
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
};
// 查找右边界（最右边的目标值）
const findRight = (nums, target) => {
let left = 0, right = nums.length - 1, result = -1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
result = mid;
left = mid + 1;
// 关键：继续向右搜索
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
};
return [findLeft(nums, target), findRight(nums, target)];
};
代码中的「坑」与「巧思」
坑点1：边界处理
// 错误的写法
if (nums[mid] === target) {
result = mid
left = mid - 1 // 应该
是 mid + 1
}
找右边界时，应该是 left = mid + 1 ，而不是 left = mid - 1 。这就像是你在找队伍的最后一个人，找到一个目标后，应该继续往后看，而不是往前看。
巧思1：为什么要用两次二分查找？
有人可能会问：「为什么不能一次二分查找解决？」
答案是： 贪心不足蛇吞象 。一次二分查找只能找到一个位置，而我们需要两个边界。就像你不能指望一次投篮就能同时投进两个篮筐一样。
巧思2：时间复杂度分析
两次二分查找：2 × O(log n) = O(log n)
空间复杂度：O(1) 完美符合题目要求！
实战演练
让我们用 nums = [5,7,7,8,8,10], target = 8 来走一遍：
查找左边界：
left=0, right=5, mid=2, nums[2]=7 < 8 → left=3
left=3, right=5, mid=4, nums[4]=8 = 8 → result=4, right=3
left=3, right=3, mid=3, nums[3]=8 = 8 → result=3, right=2
left=3, right=2 → 结束，返回 result=3 查找右边界：
left=0, right=5, mid=2, nums[2]=7 < 8 → left=3
left=3, right=5, mid=4, nums[4]=8 = 8 → result=4, left=5
left=5, right=5, mid=5, nums[5]=10 > 8 → right=4
left=5, right=4 → 结束，返回 result=4 最终结果： [3, 4] ✅
总结
这道题的精髓在于：
不要被表面的简单迷惑 ：看似简单的查找，实则需要精妙的边界处理
分而治之的智慧 ：将复杂问题拆解为两个简单的子问题
细节决定成败 ：一个 +1 和 -1 的差别，就是 AC 和 WA 的区别 记住，编程就像是在走钢丝，每一步都要小心翼翼，但掌握了技巧后，你就能在代码的世界里翩翩起舞。
「代码如诗，算法如画。愿你在二分查找的世界里，找到属于自己的那份优雅。」