二分是什么意思?二分法:深入淺出理解這一關鍵的算法
二分,又稱二分查找,是一種在有序數組中查找特定元素的有效算法。其核心思想是通過不斷將搜索范圍對半分,縮小目標元素的查找范圍,從而提高查找效率。
二分法步驟:
1. 定義搜索范圍:將數組的起始索引和結束索引設為 `[start, end]`。
2. 計算中間索引:計算數組中間索引 `mid` 為 `(start + end) / 2`,并與目標值 `target` 進行比較。
3. 目標值在左邊:如果 `target < arr[mid]`, 將 `end` 更新為 `mid - 1`。
4. 目標值在右邊:如果 `target > arr[mid]`, 將 `start` 更新為 `mid + 1`。
5. 目標值找到:如果 `target == arr[mid]`, 則目標值找到,返回 `mid`。
6. 搜索范圍縮小:如果 `start > end`, 表明沒有找到目標值,返回 `-1`。
7. 重復步驟 2 到 6:直到找到目標值或搜索范圍縮小到僅剩一個元素。
示例:
考慮一個有序數組 `arr = [1, 3, 5, 7, 9, 11, 13, 15]`,并查找目標值 `target = 7`。
步驟 1:初始搜索范圍 `[0, 7]`。
步驟 2:中間索引 `mid = (0 + 7) / 2 = 3`, `arr[3] = 7`。
步驟 3:`target == arr[mid]`, 找到目標值。返回 `mid = 3`。
代碼實現:
```python
def binary_search(arr, target):
start, end = 0, len(arr) - 1

while start <= end:
mid = (start + end) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
start = mid + 1
else:
end = mid - 1
return -1
```
性能分析:
二分法的時間復雜度為 O(log n),其中 n 為數組的長度。其平均查找次數為 log n,這意味著隨著數組大小的增加,查找過程會變得非常高效。
應用:
二分法廣泛應用于各種領域,包括但不限于:
排序算法(如快速排序和歸并排序)
二叉搜索樹
哈希表
數據壓縮
評論前必須登錄!
立即登錄 注冊