704. 二分查找

题目链接：704. 二分查找

题目描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

核心思考：标准二分查找模板与边界控制

作为计算机科学中最经典的折半搜索算法，二分查找（Binary Search）是所有算法学习者必须牢固掌握的**“背板（Template）”级标准实现。它的核心用武之地在于数组严格单调有序**。

思路虽然直观——每一次将搜索范围折半，但二分查找的精髓且最容易令开发者反复掉坑的地方在于对循环区间和收缩边界的精准把控：

1. while 循环判定（闭区间搜索）：
   当我们把左右指针的初始边界框定在 left = 0 以及 right = len(nums) - 1 时，这表明我们探索的是一个两端都包含的“闭区间” [left, right]。正因如此，当 left == right 时，区间内实质上仍有唯一的一个元素需要遭受检验。这就直接决定了我们的循环安全网必须是严苛的 while left <= right。
2. 防溢出中位值取算：
   运用 mid = left + (right - left) // 2 来取代粗暴的求和 (left + right) // 2，能够极其有效地防御强类型语言中索引游标标量过大可能引发的相加整型溢出灾难，这也标志着良好的系统级工程编码素养。
3. 彻底步进，规避死循环：
   验证过中位索引 mid 的权值与目标量大小偏差后，一旦确认不吻合，下一次的搜索雷达区间绝对不能再包容刚刚已经被定性并排斥的 mid。故而：如果是缩界至右半区，必须毫无妥协地越迁 left = mid + 1；如果是退缩至左半区，必须严格压退 right = mid - 1。稍有哪怕一个边界单位值的含糊，都有极大可能引发最终收敛阶段指针的无尽死循环卡死。

解题思路 (Python)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                # 中间值比目标值小
                # 目标在右半区
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
        return -1

复杂度分析

• 时间复杂度：$O(\log N)$，其中 $N$ 是数组的可用容量。得益于搜索辖区呈对数级的严格折半缩减，这是它超越 $O(N)$ 强力遍历最极致的降维速度优势。
• 空间复杂度：$O(1)$。算法逻辑内部无外乎增加了诸如 left、right 和 mid 此类极少量常数的定长寄存标位内存开支，属于典型彻底的原地内操作运算。