建站
咨詢
售后
建站咨詢
新聞中心
本篇內(nèi)容主要講解“Python二分查找算法怎么應(yīng)用”，感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“Python二分查找算法怎么應(yīng)用”吧!
創(chuàng)新互聯(lián)是一家專注于做網(wǎng)站、網(wǎng)站建設(shè)與策劃設(shè)計(jì),柴桑網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)十年,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:柴桑等地區(qū)。柴桑做網(wǎng)站價(jià)格咨詢:028-86922220
1. 算法描述
二分法是一種效率比較高的搜索方法
回憶之前做過的猜數(shù)字的小游戲，預(yù)先給定一個(gè)小于100的正整數(shù)x，讓你猜猜測(cè)過程中給予大小判斷的提示，問你怎樣快速地猜出來?
我們之前做的游戲給定的是10次機(jī)會(huì)，如果我們學(xué)會(huì).二分查找法以后，不管數(shù)字是多少，最多只需要7次就能猜到數(shù)字。
2. 算法分析
1、必須是有序的序列。
2、對(duì)數(shù)據(jù)量大小有要求。
數(shù)據(jù)量太小不適合二分查找，與直接遍歷相比效率提升不明顯。
數(shù)據(jù)量太大也不適合用二分查找，因?yàn)閿?shù)組需要連續(xù)的存儲(chǔ)空間，若數(shù)據(jù)量太大，往往找不到存儲(chǔ)如此大規(guī)模數(shù)據(jù)的連續(xù)內(nèi)存空間。.
3. 算法思路
假設(shè)有一個(gè)有序列表如下:
請(qǐng)問數(shù)字11是否在此列表中，如果在它的索引值為多少?
4. 代碼實(shí)現(xiàn)
純算法實(shí)現(xiàn)
實(shí)現(xiàn)代碼：
arr_list = [5, 7, 11, 22, 27, 33, 39, 52, 58]# 需要查找的數(shù)字seek_number = 11# 保存一共查找了幾次count = 0# 列表左側(cè)索引left = 0# 列表右側(cè)索引right = len(arr_list) - 1# 當(dāng)左側(cè)索引小于等于右側(cè)索引時(shí)while left <= right:
# 取中間的索引位置
middle = (left + right) // 2
# 查找次數(shù)進(jìn)行累加
count += 1
# 如果查找的數(shù)字大于中間位置的數(shù)字時(shí)
if seek_number > arr_list[middle]:
# 左側(cè)索引為中間位置索引+1
left = middle + 1
# 如果查找的數(shù)字小于中間位置的數(shù)字時(shí)
elif seek_number < arr_list[middle]:
# 右側(cè)索引為中間位置索引-1
right = middle - 1
# 如果等于中間索引數(shù)據(jù)
else:
print('數(shù)字：%s找到了，索引值為：%s' % (seek_number, middle))
breakelse:
print("數(shù)字%s 沒有找到" % seek_number)print("一共用了：%s次查找" % count)運(yùn)行結(jié)果：
遞歸法實(shí)現(xiàn)
在循環(huán)中定義了一個(gè)變量count，如果第一次循環(huán)后count沒有變化，就說明輸入的是有序序列，這時(shí)我們直接return退出循環(huán)，這時(shí)候的時(shí)間復(fù)雜度為O(n)
實(shí)現(xiàn)代碼：
arr_list = [5, 7, 11, 22, 27, 33, 39, 52, 58]def binary_search(seek_number, left, right):
if left <= right:
middle = (left + right) // 2
if seek_number < arr_list[middle]:
right = middle - 1
elif seek_number > arr_list[middle]:
left = middle + 1
else:
return middle # 進(jìn)行遞歸調(diào)用
return binary_search(seek_number, left, right)
# 當(dāng)左側(cè)索引大于右側(cè)索引時(shí)，說明沒有找到
else:
return -1# 查找的數(shù)字seek_number = 11# 列表左側(cè)索引left = 0# 列表右側(cè)索引right = len(arr_list) - 1print("查找的數(shù)字：%s，索引為：%s" % (seek_number, binary_search(seek_number, left, right)))運(yùn)行結(jié)果：
到此，相信大家對(duì)“Python二分查找算法怎么應(yīng)用”有了更深的了解，不妨來實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！
新聞名稱：Python二分查找算法怎么應(yīng)用
當(dāng)前鏈接：http://www.dlmjj.cn/article/gigepi.html
