0704.二分查找
难度：🟢 简单
标签：数组、二分查找
链接：704. 二分查找
题目描述
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1：
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2：
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
解题思路
核心思想
本题的核心是实现标准的 二分查找（Binary Search） 算法。二分查找是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束；如果目标值大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且同样是从中间元素开始比较。
思路选择
对于一个有序数组的查找问题，二分查找是最高效的算法。它利用了数组的有序性，通过不断地将搜索区间减半来快速定位目标，其时间复杂度远优于线性扫描。
关键步骤
初始化指针：定义两个指针，
left指向数组的起始位置（索引0），right指向数组的结束位置（索引nums.length - 1）。这两个指针构成了我们的搜索区间[left, right]。循环条件：当
left <= right时，表示搜索区间仍然有效，持续循环。计算中间点：计算中间索引
mid = left + Math.floor((right - left) / 2)。这种写法比(left + right) / 2更能有效防止left和right过大时相加导致的整数溢出问题。比较与收缩区间： a. 如果
nums[mid]等于target，说明找到了目标值，直接返回mid。 b. 如果nums[mid]小于target，说明目标值应该在mid的右侧，因此我们将搜索区间的左边界更新为left = mid + 1。 c. 如果nums[mid]大于target，说明目标值应该在mid的左侧，因此我们将搜索区间的右边界更新为right = mid - 1。返回结果：如果循环结束（即
left > right），说明搜索区间为空，仍未找到目标值，返回-1。
代码实现
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function (nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
// 防止溢出
let mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] < target) {
// 目标在右侧，收缩左边界
left = mid + 1;
} else {
// 目标在左侧，收缩右边界
right = mid - 1;
}
}
// 未找到目标
return -1;
};
复杂度分析
时间复杂度：O(log n) 其中 n 是数组
nums的长度。每一次比较都将搜索范围缩小一半，所以时间复杂度是对数级别的。空间复杂度：O(1) 我们只使用了
left,right,mid等常数个额外变量，空间消耗是恒定的。
相关题目
总结
二分查找是计算机科学中非常基础且重要的算法之一，是面试中的必考点。其核心在于 循环不变量 的定义，即在循环过程中始终保持搜索区间的有效性。掌握其 while (left <= right) 的闭区间写法，以及左右边界的正确收缩 (left = mid + 1, right = mid - 1)，是写出正确二分查找的关键。