您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“Python二分查找算法怎么應(yīng)用”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“Python二分查找算法怎么應(yīng)用”吧!
二分法是一種效率比較高的搜索方法
回憶之前做過的猜數(shù)字的小游戲,預(yù)先給定一個小于100的正整數(shù)x,讓你猜猜測過程中給予大小判斷的提示,問你怎樣快速地猜出來?
我們之前做的游戲給定的是10次機(jī)會,如果我們學(xué)會.二分查找法以后,不管數(shù)字是多少,最多只需要7次就能猜到數(shù)字。
1、必須是有序的序列。
2、對數(shù)據(jù)量大小有要求。
數(shù)據(jù)量太小不適合二分查找,與直接遍歷相比效率提升不明顯。
數(shù)據(jù)量太大也不適合用二分查找,因為數(shù)組需要連續(xù)的存儲空間,若數(shù)據(jù)量太大,往往找不到存儲如此大規(guī)模數(shù)據(jù)的連續(xù)內(nèi)存空間。.
假設(shè)有一個有序列表如下:
請問數(shù)字11是否在此列表中,如果在它的索引值為多少?
實現(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è)索引時while left <= right: # 取中間的索引位置 middle = (left + right) // 2 # 查找次數(shù)進(jìn)行累加 count += 1 # 如果查找的數(shù)字大于中間位置的數(shù)字時 if seek_number > arr_list[middle]: # 左側(cè)索引為中間位置索引+1 left = middle + 1 # 如果查找的數(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)
運行結(jié)果:
在循環(huán)中定義了一個變量count,如果第一次循環(huán)后count沒有變化,就說明輸入的是有序序列,這時我們直接return退出循環(huán),這時候的時間復(fù)雜度為O(n)
實現(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è)索引時,說明沒有找到 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)))
運行結(jié)果:
到此,相信大家對“Python二分查找算法怎么應(yīng)用”有了更深的了解,不妨來實際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。