Python中的二分查詢詳解

二分查詢是一種用於在已排序陣列中搜索元素的搜尋演算法。它不能用於在未排序陣列中搜索。二分查詢是一種高效的演算法，在時間複雜度方面優於線性查詢。

線性查詢的時間複雜度為O(n)。而二分查詢的時間複雜度為O(log n)。因此，二分查詢是一種高效且快速的搜尋演算法，但只能用於在已排序陣列中搜索。

二分查詢是如何工作的？

二分查詢的基本思想是，與其將所需元素與陣列的所有元素進行比較，不如將其與陣列的中間元素進行比較。如果這恰好是我們正在尋找的元素，那麼搜尋就成功完成了。否則，如果我們正在尋找的元素小於中間元素，則可以確定該元素位於陣列的前半部分或左半部分（因為陣列已排序）。類似地，如果我們正在尋找的元素大於中間元素，則可以確定該元素位於陣列的後半部分。

因此，二分查詢不斷將陣列減半。上述過程遞迴地應用於所選陣列的一半，直到找到我們正在尋找的元素。

我們將從左索引0和右索引（等於陣列的最後一個索引）開始搜尋。計算中間元素索引(mid)，它是左索引和右索引之和除以2。如果所需元素小於中間元素，則右索引更改為mid-1，這意味著我們現在只關注陣列的前半部分。同樣，如果所需元素大於中間元素，則左索引更改為mid+1，這意味著我們現在只關注陣列的後半部分。我們將對所選陣列的一半重複上述過程。

我們如何知道元素不存在於陣列中？

我們需要一些條件來停止進一步的搜尋，這將表明該元素不存在於陣列中。只要左索引小於或等於右索引，我們就將迭代地搜尋陣列中的元素。一旦此條件變為false，而我們尚未找到該元素，則表示該元素不存在於陣列中。

示例

讓我們取以下已排序陣列，我們需要搜尋元素6。

L=0 H=8 Mid=4

6<10，因此取前半部分。

H=Mid-1

L=0 H=3 Mid=1

6>5，因此選擇後半部分。

L=Mid+1

L=2 H=3 Mid=2

6==6，找到元素

因此，元素6位於索引2處。

實現

從給定的已排序陣列中，搜尋所需的元素，如果該元素存在於陣列中，則列印其索引。如果元素不存在，則列印-1。

下面給出二分查詢實現的程式碼。

示例

 線上演示

def binary_search(arr,x):
   l=0
   r=len(arr)-1
   while(l<=r):
      mid=(l+r)//2
      if(arr[mid]==x):
         return mid
      elif(x<arr[mid]):
         r=mid-1
      elif(x>arr[mid]):
         l=mid+1
   return -1
array=[1,2,3,4,5,6,7,8,9,10]
a=7
print(binary_search(array,a))
b=15
print(binary_search(array,b))

輸出

6
-1

元素7位於索引6處。

陣列中不存在元素15，因此列印-1。

pawandeep

更新於：2021年3月11日

4K+ 次瀏覽

啟動您的職業生涯

完成課程後獲得認證

開始學習