二分查找法（Binary Search）是一種在有序數(shù)組中查找某一特定元素的算法，它的思想是將數(shù)組從中間分成兩部分，判斷目標(biāo)元素在哪一部分中，然后繼續(xù)在相應(yīng)的部分中進(jìn)行查找，直到找到目標(biāo)元素或者確定目標(biāo)元素不存在為止。

在本文中，我們將使用 Python 實(shí)現(xiàn)二分查找算法，并深入探討算法的原理和實(shí)現(xiàn)細(xì)節(jié)。

1.二分查找的原理

二分查找法適用于有序數(shù)組中查找某一特定元素的場(chǎng)景，它的原理是將有序數(shù)組分成兩個(gè)部分，每次取中間位置的元素與目標(biāo)元素進(jìn)行比較，根據(jù)比較結(jié)果確定要查找的元素在左邊部分還是右邊部分，然后繼續(xù)在相應(yīng)的部分中進(jìn)行查找。

這樣每次都能將待查找區(qū)間縮小一半，直到找到目標(biāo)元素或者確定目標(biāo)元素不存在為止。

二分查找法的時(shí)間復(fù)雜度為 O(log n)，其中 n 表示數(shù)組的長(zhǎng)度。這是因?yàn)槊看尾檎叶紝⒉檎覅^(qū)間縮小一半，最壞情況下需要查找 log n 次。

2.二分查找的實(shí)現(xiàn)

接下來(lái)，我們將使用 Python 實(shí)現(xiàn)二分查找算法。首先，我們定義一個(gè)函數(shù)binary_search，接收兩個(gè)參數(shù)：一個(gè)有序數(shù)組 arr 和一個(gè)目標(biāo)元素 target。

函數(shù)返回目標(biāo)元素在數(shù)組中的下標(biāo)，如果不存在則返回 -1。

def?binary_search(arr,?target):
????left?=?0
????right?=?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

在這個(gè)函數(shù)中，我們定義了兩個(gè)指針 left 和 right，分別指向數(shù)組的第一個(gè)元素和最后一個(gè)元素。

然后，我們進(jìn)入一個(gè)循環(huán)，直到 left > right 為止。在每次循環(huán)中，我們計(jì)算中間位置的下標(biāo) mid，并將 arr[mid] 與 target 進(jìn)行比較。

如果 arr[mid] 等于 target，說(shuō)明我們已經(jīng)找到了目標(biāo)元素，直接返回 mid。如果 arr[mid] 小于 target，說(shuō)明目標(biāo)元素在右邊部分，我們將 left 指針移到 mid 的右邊一位。

如果 arr[mid] 大于 target，說(shuō)明目標(biāo)元素在左邊部分，我們將 right 指針移到 mid 的左邊一位。這樣不斷縮小查找區(qū)間，直到找到目標(biāo)元素或者確定目標(biāo)元素不存在為止。下面是一個(gè)使用例子：

arr?=?[1,?3,?5,?7,?9]
target?=?7
result?=?binary_search(arr,?target)
if?result?==?-1:
????print("Element?is?not?present?in?array")
else:
????print("Element?is?present?at?index",?result)

在這個(gè)例子中，我們定義了一個(gè)有序數(shù)組 arr 和一個(gè)目標(biāo)元素 target，并調(diào)用了 binary_search 函數(shù)。

如果目標(biāo)元素存在于數(shù)組中，函數(shù)將返回目標(biāo)元素在數(shù)組中的下標(biāo)；否則返回 -1。

在這個(gè)例子中，目標(biāo)元素 7 存在于數(shù)組中，函數(shù)將輸出 “Element is present at index 3”。

3.二分查找的優(yōu)化

雖然二分查找法的時(shí)間復(fù)雜度為 O(log n)，但是在實(shí)際應(yīng)用中，我們可以通過(guò)一些優(yōu)化來(lái)進(jìn)一步提高算法的效率。

（1）查找區(qū)間的左右邊界

在二分查找法中，我們需要定義一個(gè)查找區(qū)間，通常用 left 和 right 兩個(gè)指針來(lái)表示。

在每次循環(huán)中，我們需要判斷 left 和 right 是否重合，如果重合則說(shuō)明查找區(qū)間為空，目標(biāo)元素不存在于數(shù)組中。

這個(gè)判斷過(guò)程需要進(jìn)行多次，可以通過(guò)在循環(huán)條件中直接判斷 left 和 right 是否相鄰來(lái)減少判斷次數(shù)，如下所示：

while?left?<?right:
????mid?=?(left?+?right)?//?2
????if?arr[mid]?==?target:
????????return?mid
????elif?arr[mid]?<?target:
????????left?=?mid?+?1
????else:
????????right?=?mid?-?1
if?arr[left]?==?target:
????return?left
else:
????return?-1

在這個(gè)優(yōu)化中，我們將循環(huán)條件改為 left < right，這樣每次循環(huán)結(jié)束后，left 和 right 最多相差 1。

在循環(huán)結(jié)束后，我們需要判斷 left 和 right 是否指向目標(biāo)元素。如果 arr[left] 等于 target，則說(shuō)明目標(biāo)元素存在于數(shù)組中，返回 left；否則返回 -1。

（2）位運(yùn)算代替除法運(yùn)算

在計(jì)算中間位置的下標(biāo) mid 時(shí)，我們通常使用除法運(yùn)算符 //。然而，除法運(yùn)算符比位運(yùn)算符效率低得多，因此我們可以使用位運(yùn)算符 >> 來(lái)代替除法運(yùn)算符 //，如下所示：

mid?=?(left?+?right)?>>?1

在這個(gè)優(yōu)化中，我們將除以 2 改為右移 1 位，即將二進(jìn)制數(shù)向右移動(dòng)一位，相當(dāng)于除以 2。這樣可以減少計(jì)算中間位置的下標(biāo)所需的時(shí)間。

（3）使用 bisect 庫(kù)

Python 中的 bisect 庫(kù)提供了一些實(shí)用的函數(shù)，可以幫助我們更方便地進(jìn)行二分查找。

其中，bisect_left 函數(shù)和 bisect_right 函數(shù)分別用于在有序數(shù)組中查找某一元素的插入位置。

這兩個(gè)函數(shù)的區(qū)別在于，當(dāng)有多個(gè)相同的元素時(shí)，bisect_left 函數(shù)返回第一個(gè)位置，而 bisect_right 函數(shù)返回最后一個(gè)位置。

下面是一個(gè)使用 bisect 庫(kù)進(jìn)行二分查找的例子：

import?bisect
arr?=?[1,?3,?5,?7,?9]
target?=?7
index?=?bisect.bisect_left(arr,?target)
if?index?<?len(arr)?and?arr[index]?==?target:
????print("Element?is?present?at?index",?index)
else:
????print("Element?is?not?present?in?array")

在這個(gè)例子中，我們使用 bisect.bisect_left 函數(shù)在有序數(shù)組 arr 中查找目標(biāo)元素 target 的插入位置。

如果插入位置小于數(shù)組長(zhǎng)度，并且插入位置處的元素等于目標(biāo)元素，則說(shuō)明目標(biāo)元素存在于數(shù)組中，輸出其下標(biāo)；否則輸出 “Element is not present in array”。

4.總結(jié)

二分查找法是一種高效的查找算法，適用于有序數(shù)組中查找某一特定元素的場(chǎng)景。通過(guò)將數(shù)組從中間分成兩部分，每次取中間位置的元素與目標(biāo)元素進(jìn)行比較，可以將待查找區(qū)間縮小一半，從而降低查找的時(shí)間復(fù)雜度。

在實(shí)現(xiàn)二分查找算法時(shí)，我們需要定義一個(gè)查找區(qū)間，通常用 left 和 right 兩個(gè)指針來(lái)表示。在每次循環(huán)中，我們計(jì)算中間位置的下標(biāo) mid，并將 arr[mid] 與 target 進(jìn)行比較。如果 arr[mid] 等于 target，說(shuō)明我們已經(jīng)找到了目標(biāo)元素，直接返回 mid。

如果 arr[mid] 小于 target，說(shuō)明目標(biāo)元素在右邊部分，我們將 left 指針移到 mid 的右邊一位。如果 arr[mid] 大于 target，說(shuō)明目標(biāo)元素在左邊部分，我們將 right 指針移到 mid 的左邊一位。這樣不斷縮小查找區(qū)間，直到找到目標(biāo)元素或者確定目標(biāo)元素不存在為止。

在實(shí)際應(yīng)用中，我們可以通過(guò)一些優(yōu)化來(lái)進(jìn)一步提高算法的效率。例如，可以在循環(huán)條件中直接判斷 left 和 right 是否相鄰來(lái)減少判斷次數(shù)；可以使用位運(yùn)算符 >> 來(lái)代替除法運(yùn)算符 //，減少計(jì)算中間位置的下標(biāo)所需的時(shí)間；可以使用 bisect 庫(kù)提供的函數(shù)來(lái)進(jìn)行二分查找，更方便地實(shí)現(xiàn)算法。

到此這篇關(guān)于Python實(shí)現(xiàn)二分法查找及優(yōu)化的示例詳解的文章就介紹到這了,更多相關(guān)Python二分法查找內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論