二分查找法怎么在python項目中實現(xiàn)

發(fā)布時間：2020-12-07 15:08:01 來源：億速云閱讀：116 作者：Leah 欄目：開發(fā)技術(shù)

二分查找法怎么在python項目中實現(xiàn)？很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。

1、二分查找

在一個有序并且無重復(fù)的列表中，對該列表的元素進(jìn)行查找。

2、特點

（1）必須針對于有序列表

（2）該列表必須無重復(fù)

（3）按下標(biāo)索引查找

3、使用方法

非遞歸實現(xiàn)：

def binary_search(alist, item):
  """二分查找 非遞歸方式"""
  n = len(alist)
  start = 0
  end = n - 1
  while start <= end:
    mid = (start + end) // 2
    if alist[mid] == item:
      return True
    elif item < alist[mid]:
      end = mid - 1
    else:
      start = mid + 1
  return False

if __name__ == '__main__':
  li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
  # print(binary_search(li, 55))
  # print(binary_search(li, 100))

遞歸實現(xiàn)：

def binary_search_2(alist, item):
  """二分查找 遞歸方式"""
  n = len(alist)
  if 0 == n:
    return False
  mid = n // 2
  if alist[mid] == item:
    return True
  elif item < alist[mid]:
    return binary_search_2(alist[:mid], item)
  else:
    return binary_search_2(alist[mid + 1:], item)
if __name__ == '__main__':
  li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
  # print(binary_search(li, 55))
  # print(binary_search(li, 100))

基礎(chǔ)知識點擴(kuò)展：

介紹

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。

前提

必須待查找的序列有序

時間復(fù)雜度

O(log2n)

原理

1）確定該期間的中間位置K

2）將查找的值t與array[k]比較，若相等，查找成功返回此位置；否則確定新的查找區(qū)域，繼續(xù)二分查找。

3）區(qū)域確定過程：

若array[k]>t，由于數(shù)組有序，所以array[k,k+1,……,high]>t；故新的區(qū)間為array[low, ..., K-1]；

反之，若array[k]<t對應(yīng)查找區(qū)間為array[k+1, ..., high]

看完上述內(nèi)容是否對您有幫助呢？如果還想對相關(guān)知識有進(jìn)一步的了解或閱讀更多相關(guān)文章，請關(guān)注億速云行業(yè)資訊頻道，感謝您對億速云的支持。

向AI問一下細(xì)節(jié)

二分查找法怎么在python項目中實現(xiàn)

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽