二分查找

🟢 Easy · 🏷️ 数组、二分查找 · LeetCode#704

📖 题目

在升序数组 nums 里查找 target 的下标，不存在返回 -1。

输入	输出
nums=[-1,0,3,5,9,12], target=9	4

💡 思路

有序数组查找，每次比较中间元素就能排除掉一半区间——这就是二分查找，O(log n)。

用左闭右闭区间 [i, j] 写：i = 0, j = len(nums)-1，两端都是有效下标。这个选择会连带决定其他几处写法，四者要配套：

• 循环条件是 i <= j（区间 [i,j] 还有效，i>j 就该停了）
• m 比较完之后已经被排除，所以下一轮是 j=m-1 或 i=m+1，不能再包含 m

💻 代码

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        i, j = 0, len(nums) - 1
        while i <= j:
            m = (i + j) // 2
            if nums[m] == target:
                return m
            if nums[m] > target:
                j = m - 1   # 目标在左半边
            else:
                i = m + 1   # 目标在右半边
        return -1

时间复杂度 O(log n)，空间复杂度 O(1)。