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) - 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
)
