二分查找 (Binary Search)

1. 原理解析二分查找又名折半查找。生活中的例子假设我们在玩一个猜数字游戏数字范围是 1 到 100。我心里想了一个数字你每次猜一个数字我会告诉你“大了”、“小了”还是“猜对了”。如果你从 1 开始挨个猜1, 2, 3…最坏情况要猜 100 次。但如果你很聪明你会先猜 50如果我说“大了”你就知道答案在 1 到 49 之间。下一次你猜 25不断折半。这就是二分查找的核心思想每次排除一半的错误答案极大地缩小搜索范围。2. 使用场景前提条件数据必须是有序的从小到大或从大到小并且支持随机访问比如数组。典型场景在大量有序数据中快速定位某个特定的值或者寻找满足某个条件的边界如第一个大于某数的元素。3. 核心难点/易错点详解二分查找看起来简单但写对很难被誉为“十个二分九个错”。核心难点在于循环边界和区间更新。关键点明确你定义的“搜索区间”是什么。通常我们定义搜索区间为“左闭右闭”[left, right]初始化left 0,right array.length - 1因为索引 length-1 是可以取到的。循环条件while (left right)。为什么是因为当left right时区间内还有一个元素没检查比如区间变成了[3, 3]你得把索引为 3 的元素检查一下。如果用就会漏掉这个元素。更新区间如果array[mid] target说明目标在左半边。此时新的右边界应该是right mid - 1因为 mid 已经检查过不是目标了直接剔除。如果array[mid] target说明目标在右半边。新的左边界left mid 1。防溢出小技巧计算中间位置时不要写mid (left right) / 2。如果left和right都很大相加可能会超出整型的最大值范围导致溢出。正确写法mid left (right - left) / 2。也可以理解为“左端点加上区间长度的一半”。4. 代码实战4.1 左闭右闭写法[left, right]Python 实现defbinary_search(nums:list[int],target:int)-int:left,right0,len(nums)-1whileleftright:midleft(right-left)//2ifnums[mid]target:returnmidelifnums[mid]target:leftmid1else:rightmid-1return-1Java 实现publicclassBinarySearch{publicintsearch(int[]nums,inttarget){intleft0;intrightnums.length-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){returnmid;}elseif(nums[mid]target){leftmid1;}else{rightmid-1;}}return-1;}}4.2 左闭右开写法[left, right)补充拓展Python 实现defbinary_search_open(nums:list[int],target:int)-int:left,right0,len(nums)# right 取不到 len(nums)# 因为 right 取不到所以 left right 时区间为空循环条件不能带等号whileleftright:midleft(right-left)//2ifnums[mid]target:returnmidelifnums[mid]target:leftmid1else:rightmid# 右边界取不到设为 mid 刚好排除 mid 本身return-1Java 实现publicclassBinarySearchOpen{publicintsearch(int[]nums,inttarget){intleft0;intrightnums.length;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){returnmid;}elseif(nums[mid]target){leftmid1;}else{rightmid;}}return-1;}}5. 复杂度分析时间复杂度O(log⁡N)O(\log N)O(logN)。每次循环将搜索范围缩小一半假设总共有NNN个元素最多需要找log⁡2(N)\log_2(N)log2​(N)次。这是极其高效的比如 40 亿个数字中找一个最多只需 32 次。空间复杂度O(1)O(1)O(1)。我们只使用了几个整型变量left, right, mid没有额外申请数组空间。