av一区二区在线观看_亚洲男人的天堂网站_日韩亚洲视频_在线成人免费_欧美日韩精品免费观看视频_久草视

您的位置:首頁技術(shù)文章
文章詳情頁

Python查找算法之折半查找算法的實現(xiàn)

瀏覽:3日期:2022-06-23 08:52:48
一、折半查找算法

折半查找算法又稱為二分查找算法,折半查找算法是將數(shù)據(jù)分割成兩等份,首先用鍵值(要查找的數(shù)據(jù))與中間值進(jìn)行比較。如果鍵值小于中間值,可確定要查找的鍵值在前半段;如果鍵值大于中間值,可確定要查找的鍵值在后半段。然后對前半段(后半段)進(jìn)行分割,將其分成兩等份,再對比鍵值。如此循環(huán)比較、分割,直到找到數(shù)據(jù)或者確定數(shù)據(jù)不存在為止。折半查找的缺點是只適用于已經(jīng)初步排序好的數(shù)列;優(yōu)點是查找速度快。

生活中也有類似于折半查找的例子,例如,猜數(shù)字游戲。在游戲開始之前,首先會給出一定的數(shù)字范圍(例如0~100),并在這個范圍內(nèi)選擇一個數(shù)字作為需要被猜的數(shù)字。然后讓用戶去猜,并根據(jù)用戶猜的數(shù)字給出提示(如猜大了或猜小了)。用戶通常的做法就是先在大范圍內(nèi)隨意說一個數(shù)字,然后提示猜大了/猜小了,這樣就縮小了猜數(shù)字的范圍,慢慢地就猜到了正確的數(shù)字,如下圖所示。這種做法與折半查找法類似,都是通過不斷縮小數(shù)字范圍來確定數(shù)字,如果每次猜的范圍值都是區(qū)間的中間值,就是折半查找算法了。

Python查找算法之折半查找算法的實現(xiàn)

例如,已經(jīng)有 排序好 的數(shù)列:12、45、56、66、77、80、97、101、120,要查找的數(shù)據(jù)是 101,用折半查找步驟如下:

步驟1:將數(shù)據(jù)列出來并找到中間值 77,將 101 與 77 進(jìn)行比較,如下圖所示。

Python查找算法之折半查找算法的實現(xiàn)

步驟2:將 101 與 77 進(jìn)行比較,結(jié)果是 101 大于 77,說明要查找的數(shù)據(jù)在數(shù)列的右半段。此時不考慮左半段的數(shù)據(jù),對在右半段的數(shù)據(jù)再進(jìn)行分割,找中間值。這次中間值的位置在 97 和 101 之間,取 97,將 101 與 97 進(jìn)行比較,如下圖所示。

Python查找算法之折半查找算法的實現(xiàn)

步驟3:將 101 與 97 進(jìn)行比較,結(jié)果是 101 大于 97,說明要查找的數(shù)據(jù)在右半段數(shù)列中,此時不考慮左半段的數(shù)據(jù),再對剩下的數(shù)列分割,找中間值,這次中間值位置是 101,將 101 與 101 進(jìn)行比較,如下圖所示。

Python查找算法之折半查找算法的實現(xiàn)

步驟4:將 101 與 101 進(jìn)行比較,所得結(jié)果相等,查找完成。說明:如果多次分割之后沒有找到相等的值,表示這個鍵值沒有在這個數(shù)列中。

從折半法查找的步驟來看,明顯比順序查找法的次數(shù)少,這就是折半查找法的優(yōu)點:查找速度快。

二、實例:線路故障

有一條的150米線路,在這條線路上存在故障。第一天維修工已經(jīng)大致鎖定了幾個疑似故障點,疑似故障點分別在線路的12、45、56、66、77、80、97、101、120米處。第二天維修工要在這9個疑似故障點中確定一個真正的故障點(假設(shè)真正的故障點是101米處)。維修工為了快速查找此故障點,就在每段數(shù)據(jù)的中間位置開始排查。

例如,第一次選擇在77米處的疑似故障點接通電路,發(fā)現(xiàn)接通,他判斷此故障在77米之后的位置;第二次取97米處的疑似故障點,發(fā)現(xiàn)也接通了,說明在97米之后的位置;第三次取101米處的位置,再次接通線路,發(fā)現(xiàn)未接通,說明此處是真正的故障點。此次查找經(jīng)歷了3次,將真正故障點找到。具體代碼如下:

def search(data, num): ''' 定義查找函數(shù):該函數(shù)使用的是折半查找算法 :param data: 原數(shù)列data :param num: 鍵值num :return: ''' low = 0 # 定義變量用來表示低位 high = len(data) - 1 # 定義變量用來表示高位 print('正在查找.......') # 提示 while low <= high and num != -1:mid = int((low + high) / 2) # 取中間位置if num < data[mid]: # 判斷數(shù)據(jù)是否小于中間值 # 輸出位置在數(shù)列中的左半邊 print(f'{num} 介于中間故障點 {low + 1}[{data[low]}] 和故障點位置 {mid + 1}[{data[mid]}] 之間,找左半邊......') high = mid - 1 # 最高位變成了中間位置減1elif num > data[mid]: # 判斷數(shù)據(jù)是否大于中間值 # 輸出位置在數(shù)列中的右半邊 print(f'{num} 介于中間故障點 {mid + 1}[{data[mid]}] 和故障點位置 {high + 1}[{data[high]}] 之間,找右半邊......') low = mid + 1 # 最低位變成了中間位置加1else: # 判斷數(shù)據(jù)是否等于中間值 return mid # 返回中間位置 return -1 # 自定義函數(shù)到此結(jié)束inp_num = 0 # 定義變量,用來輸入鍵值num_list = [12, 45, 56, 66, 77, 80, 97, 101, 120] # 定義數(shù)列print('疑似故障點如下:')for index, ele in enumerate(num_list): print(f' {index + 1}[{ele}]', end='') # 輸出數(shù)列print('')flag = True # 開關(guān),用來管控是否多次查找while flag: # 循環(huán)查找 inp_num = int(input('請輸入故障點:').strip()) # 輸入查找鍵值 if inp_num == -1: # 判斷鍵值是否是-1break # 若為-1,跳出循環(huán) 即結(jié)束程序 result = search(num_list, inp_num) # 調(diào)用自定義的查找函數(shù)——search()函數(shù) if result == -1: # 判斷查找結(jié)果是否是-1print(f'沒有找到[{inp_num}]故障點') # 若為-1,提示沒有找到值 else:# 若不為-1,提示查找位置print(f'在{result + 1}個位置找到[{num_list[result]}]故障點') char = input('本次查找結(jié)束,是否繼續(xù)查找,請輸入 y(Y) 或 n(N):').strip() if char.upper() == 'N':flag = False

程序執(zhí)行結(jié)果如下圖所示:

Python查找算法之折半查找算法的實現(xiàn)

到此這篇關(guān)于Python查找算法之折半查找算法的實現(xiàn)的文章就介紹到這了,更多相關(guān)Python 折半查找算法內(nèi)容請搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)!

標(biāo)簽: Python 編程
相關(guān)文章:
主站蜘蛛池模板: 欧美高清视频在线观看 | 久久精品国产久精国产 | 亚洲天堂男人的天堂 | av免费看在线 | 欧美亚洲日本 | 日本超碰 | 日韩毛片视频 | 国产一级片网站 | 亚洲精品视频免费 | 国产乱码精品一区二区三区忘忧草 | 美女黄网站视频免费 | 成人亚洲在线 | 日韩在线观看中文字幕 | 欧美一区二区三区在线 | 天天干夜夜拍 | 国产成人精品一区二区三区网站观看 | 中文字幕在线观看 | 手机av在线 | 国产97久久 | 国产一级片一区二区 | 精品国产乱码久久久久久影片 | 天天躁日日躁狠狠的躁天龙影院 | 91视频正在播放 | 久久a久久 | 黄色日本视频 | 九九热国产视频 | 2019中文字幕视频 | 国产福利91精品 | 成人免费影院 | 午夜精品久久久久久久久久久久 | 日本午夜精品 | 在线免费观看a级片 | 亚洲欧美一区二区三区视频 | 亚洲成人综合在线 | 一区二区三区免费观看 | 国产成人精品午夜 | 亚洲精品久久久久久首妖 | 中文字幕乱码亚洲精品一区 | 亚洲精品乱码久久久久久9色 | 精品国产18久久久久久二百 | 国产成人99久久亚洲综合精品 |