Python二分查找【清晰易懂】

1. 二分查找是什么？

想象你在玩“猜数字”游戏：

• 对方心里想一个 1~100 的数字，你每次猜一个数，对方会告诉你是“大了”还是“小了”。

• 最快的方法：每次都猜中间的数！比如第一次猜50，如果大了，就猜25；如果小了，就猜75。

• 这样每次都能排除一半的可能性，最多7次就能猜中（因为2^7=128>100）！

这就是二分查找的核心思想——每次砍掉一半的搜索范围。

---

2. 二分查找的条件

• 必须是有序的列表（比如从小到大排列的数字）。

• 如果列表是乱序的，二分查找会失效。

---

3. 代码示例（Python）

def binary_search(arr, target):left, right = 0, len(arr) - 1  # 初始化搜索范围：整个列表while left <= right:mid = (left + right) // 2  # 取中间位置if arr[mid] == target:return mid  # 找到了，返回索引elif arr[mid] < target:left = mid + 1  # 目标在右半部分else:right = mid - 1  # 目标在左半部分return -1  # 没找到# 测试
nums = [1, 3, 5, 7, 9]
print(binary_search(nums, 5))  # 输出2（因为5的索引是2）
print(binary_search(nums, 4))  # 输出-1（4不在列表中）

4. 复杂二分查找题目示例

在旋转有序数组中搜索目标值

题目描述

假设一个按升序排列的数组在某个未知点进行了旋转（例如 [0,1,2,4,5,6,7] 旋转后可能变成 [4,5,6,7,0,1,2]）。
给定一个目标值 target，如果它存在于旋转后的数组中，则返回其索引，否则返回 -1。
要求时间复杂度为 O(log n)。

示例 1：

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4（0的索引是4）

示例 2：

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1（3不存在）

解题思路

处理局部有序性

旋转有序数组由两个升序子数组组成（例如 [4,5,6,7,0,1,2] 分为 [4,5,6,7] 和 [0,1,2]）。

• 左半部分：所有元素 ≥ 第一个元素（如 4,5,6,7 ≥ 4）。

• 右半部分：所有元素 < 第一个元素（如 0,1,2 < 4）。

需要区分左半部分还是右半部分是因为二分查找依赖有序性，只有确定 mid 在哪个部分，才能正确判断 target 可能的位置。

直观例子

以数组 [4,5,6,7,0,1,2] 和 target=0 为例：

1. 初始状态：left=0，right=6，mid=3（值 7）。

   nums[3] >= nums[0]（7 >= 4）→ mid 在左半部分。target=0 不在 [4,7) 范围内 → 调整 left=4。

2. 下一轮：left=4，right=6，mid=5（值 1）。

   nums[5] < nums[4]（1 < 0 不成立）→ mid 在右半部分。target=0 不在 (1,2] 范围内 → 调整 right=4。

3. 找到目标：nums[4] == 0，返回索引 4。

代码实现

def search(nums, target):left, right = 0, len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return mid# 判断mid位于左半部分还是右半部分if nums[mid] >= nums[left]:  # mid在左半部分（较大的一半）if nums[left] <= target < nums[mid]:right = mid - 1  # target在左半部分的左侧else:left = mid + 1   # target在左半部分的右侧或右半部分else:  # mid在右半部分（较小的一半）if nums[mid] < target <= nums[right]:left = mid + 1    # target在右半部分的右侧else:right = mid - 1   # target在右半部分的左侧或左半部分return -1# 测试
nums = [4,5,6,7,0,1,2]
print(search(nums, 0))  # 输出4
print(search(nums, 3))  # 输出-1