快捷導(dǎo)航

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

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

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

二分查找是一種高效的搜索算法，用于在有序數(shù)組中查找特定元素。它的思想是將查找范圍逐漸縮小一半，直到找到目標(biāo)元素或確定目標(biāo)元素不存在。本文將介紹二分查找的基本原理，并通過Python代碼進(jìn)行詳細(xì)講解。

一、原理

二分查找的原理非常簡(jiǎn)單，基本步驟如下：

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

2.計(jì)算中間點(diǎn)的位置，并取得中間點(diǎn)的值。

3.將中間點(diǎn)的值與目標(biāo)值進(jìn)行比較。

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

4.重復(fù)步驟2和步驟3，直到找到目標(biāo)元素或確定目標(biāo)元素不存在。

二、示例代碼

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

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

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

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

    return -1  # 目標(biāo)元素不存在

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

三、使用示例

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

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

輸出結(jié)果為：