Python優(yōu)雅實現(xiàn)二分查找的示例詳解

更新時間：2023年07月28日 16:36:42 作者：ziwu

二分查找是一種高效的搜索算法，用于在有序數(shù)組中查找特定元素，本文將介紹二分查找的基本原理，并通過Python代碼進行詳細講解，需要的可以參考一下

一、原理

二分查找的原理非常簡單，基本步驟如下：

1.確定查找范圍的起始點和終點。通常情況下，起始點為數(shù)組的第一個元素，終點為數(shù)組的最后一個元素。

2.計算中間點的位置，并取得中間點的值。

3.將中間點的值與目標值進行比較。

如果中間點的值等于目標值，說明已經(jīng)找到了目標元素，查找成功。
如果中間點的值大于目標值，說明目標元素可能在左半部分，將查找范圍縮小到左半部分。
如果中間點的值小于目標值，說明目標元素可能在右半部分，將查找范圍縮小到右半部分。

4.重復步驟2和步驟3，直到找到目標元素或確定目標元素不存在。

二、示例代碼

下面是使用Python實現(xiàn)二分查找算法的示例代碼：

def binary_search(arr, target):
    """
    二分查找算法
    :param arr: 有序數(shù)組
    :param target: 目標元素
    :return: 目標元素的索引，如果不存在則返回-1
    """
    low = 0  # 查找范圍的起始點
    high = len(arr) - 1  # 查找范圍的終點

    while low <= high:
        mid = (low + high) // 2  # 計算中間點的位置
        guess = arr[mid]  # 獲取中間點的值

        if guess == target:  # 如果中間點的值等于目標值，查找成功
            return mid
        elif guess > target:  # 如果中間點的值大于目標值，說明目標元素可能在左半部分
            high = mid - 1  # 將查找范圍縮小到左半部分
        else:  # 如果中間點的值小于目標值，說明目標元素可能在右半部分
            low = mid + 1  # 將查找范圍縮小到右半部分

    return -1  # 目標元素不存在

這段代碼定義了一個 binary_search 函數(shù)，接受一個有序數(shù)組 arr 和目標值 target 作為參數(shù)。函數(shù)使用 low 和 high 來表示查找范圍的起始點和終點，初始時起始點為數(shù)組的第一個元素，終點為數(shù)組的最后一個元素。在每次循環(huán)中，根據(jù)中間點的值和目標值的大小關系，更新查找范圍的起始點和終點，以逐漸縮小查找范圍。如果找到目標元素，則返回目標元素的索引；如果目標元素不存在于數(shù)組中，則返回-1。

三、使用示例

接下來，我們將使用示例來演示二分查找的使用方法。假設有一個有序數(shù)組 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]，我們要查找元素 11 的索引。我們可以使用 binary_search 函數(shù)來進行查找：

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 11
result = binary_search(arr, target)
if result != -1:
    print("目標元素的索引為:", result)
else:
    print("目標元素不存在")

輸出結果為：