快捷導(dǎo)航

python二分查找搜索算法的多種實現(xiàn)方法

更新時間：2024年03月06日 14:50:25 作者：星星貓

二分查找,也稱折半查找,是一種效率較高的查找方法,本文主要介紹了python二分查找搜索算法的多種實現(xiàn)方法,具有一定的參考價值,感興趣的可以了解一下

將 x 與中間元素進行比較。
如果 x 與中間元素匹配，則返回中間索引。
否則，如果 x 大于 mid 元素，則 x 只能位于 mid 元素之后的右（大）半子數(shù)組中。然后，我們再次將該算法應(yīng)用于右半部分。
否則，如果 x 較小，則目標(biāo) x 必須位于左（下）半部分。因此，我們將算法應(yīng)用于左半部分。

使用遞歸進行二分查找搜索

# Python 3 program for recursive binary search.
# Modifications needed for the older Python 2 are found in comments.

# Returns index of x in arr if present, else -1
def binary_search(arr, low, high, x):

    # Check base case
    if high >= low:

        mid = (high + low) // 2

        # If element is present at the middle itself
        if arr[mid] == x:
            return mid

        # If element is smaller than mid, then it can only
        # be present in left subarray
        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x)

        # Else the element can only be present in right subarray
        else:
            return binary_search(arr, mid + 1, high, x)

    else:
        # Element is not present in the array
        return -1

# Test array
arr = [ 2, 3, 4, 10, 40 ]
x = 10

# Function call
result = binary_search(arr, 0, len(arr)-1, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")

輸出

Element is present at index 3

使用迭代進行搜索

# Iterative Binary Search Function
# It returns index of x in given array arr if present,
# else returns -1
def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0

    while low <= high:

        mid = (high + low) // 2

        # If x is greater, ignore left half
        if arr[mid] < x:
            low = mid + 1

        # If x is smaller, ignore right half
        elif arr[mid] > x:
            high = mid - 1

        # means x is present at mid
        else:
            return mid

    # If we reach here, then the element was not present
    return -1


# Test array
arr = [ 2, 3, 4, 10, 40 ]
x = 10

# Function call
result = binary_search(arr, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")

輸出

Element is present at index 3

使用內(nèi)置 bisect 模塊

循序漸進的方法：

該代碼導(dǎo)入 bisect 模塊，該模塊提供對二進制搜索的支持。
定義了 binary_search_bisect（）函數(shù)，該函數(shù)將數(shù)組 arr 和搜索 x 的元素作為輸入。
該函數(shù)調(diào)用 bisect 模塊的 bisect_left（）函數(shù)，該函數(shù)在排序數(shù)組 arr 中查找元素的位置，其中應(yīng)插入 x 以保持排序順序。如果該元素已存在于數(shù)組中，則此函數(shù)將返回其位置。
然后，該函數(shù)檢查返回的索引 i 是否在數(shù)組范圍內(nèi)，以及該索引處的元素是否等于 x。
如果條件為 true，則該函數(shù)返回索引 i 作為元素在數(shù)組中的位置。
如果條件為 false，則該函數(shù)返回 -1，指示該元素不存在于數(shù)組中。
然后，代碼定義一個數(shù)組 arr 和一個要搜索的元素 x。
使用 arr 和 x 作為輸入調(diào)用 binary_search_bisect（）函數(shù)，返回的結(jié)果存儲在 result 變量中。
然后，代碼檢查結(jié)果是否不等于 -1，指示該元素存在于數(shù)組中。如果為 true，則打印元素在數(shù)組中的位置。
如果結(jié)果等于 -1，則代碼將打印一條消息，指出該元素在數(shù)組中不存在。

import bisect

def binary_search_bisect(arr, x):
    i = bisect.bisect_left(arr, x)
    if i != len(arr) and arr[i] == x:
        return i
    else:
        return -1


# Test array
arr = [2, 3, 4, 10, 40]
x = 10

# Function call
result = binary_search_bisect(arr, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")

輸出