python中二分查找法的實(shí)現(xiàn)方法

更新時(shí)間：2020年12月06日 12:03:28 作者：宋宋大人

在本篇內(nèi)容里小編給大家整理了關(guān)于python中二分查找法的實(shí)現(xiàn)方法，有需要的朋友們可以學(xué)習(xí)下。

如果想要在有序數(shù)據(jù)中進(jìn)行查找想要的數(shù)據(jù)，二分查找法就個(gè)好方法，它可以大大縮短了搜索時(shí)間，是一種常見的查找方法。二分查找很好寫，卻很難寫對(duì)，下面，小編就簡(jiǎn)單向大家介紹一下二分查找，并演示器使用代碼。

1、二分查找

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

2、特點(diǎn)

（1）必須針對(duì)于有序列表

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

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

3、使用方法

非遞歸實(shí)現(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))

遞歸實(shí)現(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ǔ)知識(shí)點(diǎn)擴(kuò)展：

介紹

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

前提

必須待查找的序列有序

時(shí)間復(fù)雜度

O(log2n)

原理

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

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

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

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

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

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

您可能感興趣的文章:

相關(guān)文章

Python高并發(fā)和多線程有什么關(guān)系
這篇文章主要介紹了Python高并發(fā)和多線程有什么關(guān)系,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
2020-11-11
python實(shí)現(xiàn)圖片轉(zhuǎn)字符畫
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)圖片轉(zhuǎn)字符畫，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2021-02-02
利用Pytorch實(shí)現(xiàn)簡(jiǎn)單的線性回歸算法
今天小編就為大家分享一篇利用Pytorch實(shí)現(xiàn)簡(jiǎn)單的線性回歸算法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
2020-01-01
用Python從0開始實(shí)現(xiàn)一個(gè)中文拼音輸入法的思路詳解
中文輸入法是一個(gè)歷史悠久的問(wèn)題，但也實(shí)在是個(gè)繁瑣的活，不知道這是不是網(wǎng)上很少有人分享中文拼音輸入法的原因，接下來(lái)通過(guò)本文給大家分享使用Python從0開始實(shí)現(xiàn)一個(gè)中文拼音輸入法,需要的朋友可以參考下
2019-07-07
Pycharm?debug程序,跳轉(zhuǎn)至指定循環(huán)條件/循環(huán)次數(shù)問(wèn)題
這篇文章主要介紹了Pycharm?debug程序,跳轉(zhuǎn)至指定循環(huán)條件/循環(huán)次數(shù)問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
2023-08-08
Python全角與半角之間相互轉(zhuǎn)換的方法總結(jié)
全角與半角轉(zhuǎn)換在處理漢語(yǔ)語(yǔ)料中會(huì)經(jīng)常出現(xiàn),這里分別說(shuō)明漢字、數(shù)字、字母的unicode編碼范圍,下面這篇文章主要給大家介紹了關(guān)于Python全角與半角之間相互轉(zhuǎn)換的相關(guān)資料,需要的朋友可以參考下
2022-03-03
Python?filter函數(shù)的具體使用
在Python編程中，filter()函數(shù)是一個(gè)有用的工具，用于篩選可迭代對(duì)象（如列表、元組等）中滿足特定條件的元素，本文就來(lái)詳細(xì)的介紹一下Python?filter函數(shù)的具體使用，感興趣的可以了解一下
2024-01-01
教你怎么用Python實(shí)現(xiàn)多路徑迷宮
這篇文章主要介紹了教你怎么用Python實(shí)現(xiàn)多路徑迷宮,文中有非常詳細(xì)的代碼示例,對(duì)正在學(xué)習(xí)python的小伙伴們有非常好的幫助,需要的朋友可以參考下
2021-04-04
Python Matplotlib庫(kù)實(shí)現(xiàn)畫局部圖
這篇文章主要為大家詳細(xì)介紹了Python Matplotlib庫(kù)實(shí)現(xiàn)畫局部圖，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2021-11-11
快速入手Python字符編碼
本文不談復(fù)雜的理論，就經(jīng)驗(yàn)教大家字符處理八字真言：確定編碼，同類交互。教大家快速戰(zhàn)勝Python字符編碼。
2016-08-08