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 为例：
-
初始状态：
left=0，right=6，mid=3（值7）。nums[3] >= nums[0]（7 >= 4）→mid在左半部分。target=0不在[4,7)范围内 → 调整left=4。 -
下一轮：
left=4，right=6，mid=5（值1）。nums[5] < nums[4]（1 < 0不成立）→mid在右半部分。target=0不在(1,2]范围内 → 调整right=4。 -
找到目标：
nums[4] == 0，返回索引4。
代码实现
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if 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