1、搜索

搜索是在一個(gè)項(xiàng)目集合中找到一個(gè)特定項(xiàng)目的算法過程。搜索通常的答案是真或假，因?yàn)樵擁?xiàng)目是否存在。搜索的幾種常見方法：順序查找、二分法查找、二叉樹查找、哈希查找。

2、二分法查找

二分法查找又稱折半查找，優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好；缺點(diǎn)是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。首先，假設(shè)表中的元素是按升序排序，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分為前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，知道找到滿足條件的記錄。使查找成功，或直到子表不存在為止，此時(shí)查找不成功。

3、python代碼實(shí)現(xiàn)

3.1、遞歸方式

def binary_search(alist, item):"""二分查找——遞歸"""n = len(alist)mid = n // 2if n > 0:# 如果存在元素，返回 Trueif alist[mid] == item:return True# 如果 目標(biāo)元素 小于 alist的中間值索引對(duì)應(yīng)的索引elif item < alist[mid]:return binary_search(alist[:mid], item)# 否則，就在右邊else:return binary_search(alist[mid+1:], item)return False

3.2、非遞歸

def binary_search_2(alist, item):"""二分查找——非遞歸"""n = len(alist)first = 0last = n-1while first <= last:mid = (first+last) // 2if alist[mid] == item:return True# 如果 目標(biāo)值 在右側(cè)，將last等于中間值的左側(cè)第一個(gè)elif item < alist[mid]:last = mid - 1# 如果在左側(cè)，將first等于中間值右邊第一個(gè)else:first = mid + 1return False

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

• 最優(yōu)時(shí)間復(fù)雜度： O(1)
• 最壞時(shí)間復(fù)雜度： O(nlogn)

總結(jié)

以上是生活随笔為你收集整理的二分查找及时间复杂度的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。