704. 二分查找
题目描述
输入一个按升序排列、元素互不相同的整数数组 nums，以及目标值 target。
如果 target 在数组中，返回它的下标（从 0 开始）；否则返回 -1。
算法的时间复杂度必须是 O(log n)。
示例 1
输入：nums = [-1,0,3,5,9,12], target = 9 输出：4
解释：9 位于下标 4。
示例 2
输入：nums = [-1,0,3,5,9,12], target = 2 输出：-1
解释：数组里没有 2。
数据范围
nums中的元素互不相同。n在[1, 10000]之间。nums的每个元素在[-9999, 9999]之间。
解题思路
维护闭区间 [lo, hi] 作为 target 可能出现的范围。每次看中点：等于就返回；nums[mid] 小于 target，说明 mid 及左边都太小，lo = mid + 1；否则 mid 及右边都太大，hi = mid - 1。区间为空就说明不存在。
为什么正确
若 target 存在，它的下标一定在闭区间 [lo, hi] 中。
复杂度分析
时间 O(log n)，空间 O(1)。
易错点
闭区间写法循环条件要用 lo <= hi，收缩时用 mid ± 1；混用 lo < hi 或 hi = mid 会漏掉最后一个元素或死循环。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def search(self, nums: List[int], target: int) -> int:
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1class Solution {
public int search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return -1;
}
}class Solution {
public:
int search(vector<int>& nums, int target) {
int lo = 0, hi = (int)nums.size() - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return -1;
}
};func search(nums []int, target int) int {
lo, hi := 0, len(nums)-1
for lo <= hi {
mid := (lo + hi) / 2
if nums[mid] == target {
return mid
}
if nums[mid] < target {
lo = mid + 1
} else {
hi = mid - 1
}
}
return -1
}var search = function(nums, target) {
let lo = 0, hi = nums.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (nums[mid] === target) {
return mid;
}
if (nums[mid] < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return -1;
};function search(nums: number[], target: number): number {
let lo = 0, hi = nums.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (nums[mid] === target) {
return mid;
}
if (nums[mid] < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return -1;
}