二分查找算法是一種高效的查找算法,可以用于在有序數組中查找特定元素。其基本思想是將查找區間不斷二分,然后根據中間元素與目標元素的大小關系,縮小查找區間,直到找到目標元素或者確定目標元素不存在。
以下是一個簡單的示例代碼,演示了二分查找算法的應用:
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
# 示例用法
arr = [1, 3, 5, 7, 9, 11, 13]
target = 5
result = binary_search(arr, target)
if result != -1:
print("目標元素在數組中的索引為", result)
else:
print("目標元素不在數組中")
上述示例中,binary_search
函數接受一個有序數組arr
和一個目標元素target
作為參數,返回目標元素在數組中的索引。如果目標元素不存在于數組中,則返回-1。
在示例中,算法首先定義了查找區間的左右邊界left
和right
,初始時分別為數組的第一個和最后一個元素的索引。然后進入一個循環,每次循環將查找區間二分為兩個子區間,然后根據中間元素與目標元素的大小關系,更新左右邊界。如果中間元素等于目標元素,則找到目標元素,返回其索引。如果中間元素小于目標元素,則目標元素應該在右子區間中,更新左邊界為中間元素的下一個位置。如果中間元素大于目標元素,則目標元素應該在左子區間中,更新右邊界為中間元素的上一個位置。循環結束條件是左邊界大于右邊界。
通過二分查找算法,可以快速地在有序數組中查找目標元素,時間復雜度為O(log n)。