Step1:將數據集合按照某種規則排序,以保證數據的有序性。
Step2:確定搜索範圍的左右邊界,通常初始時為整個數據集合。
Step3:找到搜索範圍的中間元素,與目標值進行比較。
Step4:如果中間元素等於目標值,則搜索成功,返回該元素的索引。
Step5:如果中間元素大於目標值,則縮小搜索範圍為左半部分,並重複步驟3;如果中間元素小於目標值,則縮小搜索範圍為右半部分,並重複步驟3。
Step7:重複上述步驟,直到搜索範圍為空,表示目標值不在數據集合中。
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
mid_val = arr[mid]
if mid_val == target:
return mid
elif mid_val < target:
left = mid + 1
else:
right = mid - 1
return -1