c++與python實現(xiàn)二分查找的原理及實現(xiàn)
在計算機中,數(shù)據(jù)的查找方式與其存儲方式關系密切。試想一下,如果圖書館中書籍雜亂無章的存放,那么要想找到心儀的書籍將會非常困難。為此,人們常常將物品按照某種規(guī)則或次序進行放置,目的是便于日后的查找。
作為查找算法家族中的一員,二分查找正是利用數(shù)據(jù)按次序存儲這一優(yōu)點,極大的提升了查找目標值所在位置的速度。
二分查找的核心思想是:首先將數(shù)組中間值和目標值進行比較,如果相等則返回;如果不相等,則選擇中間值左邊的一半或者右邊的一半進行比較;不斷重復直到檢索完畢。首先來看下面這個gif,其中藍色圈表示左位置,粉色圈表示右位置,綠色圈表示中間位置:
首先定義的是左邊界(藍色圈)和右邊界(粉色圈),進而根據(jù)左邊界和右邊界計算出中間位置(綠色圈);然后,比較中間位置的值和目標值的大小,比較結(jié)果包含3種情況
- 如果相等則表示查找成功,返回中間位置;
- 如果中間位置的值小于目標值,則說明目標值在中間位置到右邊界這一半;
- 如果中間位置的值大于目標值,則說明目標值在左邊界到中間位置這一半;
上述步驟的循環(huán)需要終止條件,即左邊界小于或等于右邊界,表明此時已經(jīng)搜索完成,目標數(shù)值不在數(shù)據(jù)中存在。
1、時間復雜度與優(yōu)缺點
既然每次搜索后區(qū)間長度都減半,假設數(shù)據(jù)個數(shù)(即區(qū)間長度)為n,那么算法每次迭代得到的區(qū)間長度依次為n/2,n/4,n/8等等,其通項如下,k表示循環(huán)次數(shù):
最壞的情況,就是搜索到區(qū)間長度為1,即最后只剩1個元素:
所以,可以求得最壞情況下需要運行的次數(shù)為:
因此二分查找復雜度為O(logn),相比于順序查找其速度獲得了極大的提高(優(yōu)點)。但是,必須注意二分查找需要保證數(shù)據(jù)是有序的,這就要求數(shù)據(jù)必須預先進行排序(缺點)。
2、python實現(xiàn)
def binary_search(ordered_list, target_value): ? ? """ ? ? Args: ? ? ? ? ordered_list: data with order ? ? ? ? target_value: value that want be searched ? ? """ ? ? left = 0 ? ? right = len(ordered_list)-1 ? ? # 終止條件 ? ? while left <= right: ? ? ? ? # 中間位置計算 ? ? ? ? mid = int((left+right)/2) ? ? ? ? if ordered_list[mid] == target_value: ? ? ? ? ? ? return "index is {}, target value is {}".format(mid, ordered_list[mid]) ? ? ? ? # 此時目標值在中間值右邊,更新左位置 ? ? ? ? elif ordered_list[mid] < target_value: ? ? ? ? ? ? left = mid + 1 ? ? ? ? # 此時目標值在中間值左邊,更新右位置 ? ? ? ? elif ordered_list[mid] > target_value: ? ? ? ? ? ? right = mid - 1 ? ? # 搜索結(jié)束沒有找到 ? ? return "Not find"
3、C++實現(xiàn)
int binarySearch(int *orderedData, int dataLength, int targetValue) { ?? ?int left = 0; ?? ?int right = dataLength - 1; ?? ?int mid; ?? ?// 終止條件 ?? ?while (left<=right) ?? ?{ ?? ??? ?// 中間位置計算 ?? ??? ?mid = (left + right) / 2; ?? ??? ?if (*(orderedData + mid) == targetValue) { ?? ??? ??? ?return mid; ?? ??? ?} ?? ??? ?// 目標值在中間值右邊,更新左位置 ?? ??? ?else if (*(orderedData + mid) < targetValue){ ?? ??? ??? ?left = mid + 1; ?? ??? ?} ?? ??? ?// 目標值在中間值左邊,更新右位置 ?? ??? ?else ?? ??? ?{ ?? ??? ??? ?right = mid - 1; ?? ??? ?} ?? ?} ?? ?// 搜索不到,返回-1 ?? ?return -1; }
到此這篇關于c++與python實現(xiàn)二分查找的原理及實現(xiàn)的文章就介紹到這了,更多相關c++與python實現(xiàn)二分查找內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
- Python與C++中梯度方向直方圖的實現(xiàn)
- C++和python實現(xiàn)單鏈表及其原理
- c++和python實現(xiàn)順序查找實例
- python?與c++相互調(diào)用實現(xiàn)
- python直接調(diào)用和使用swig法方調(diào)用c++庫
- 如何利用Python實現(xiàn)簡單C++程序范圍分析
- 如何在C++中調(diào)用python代碼你知道嗎
- C++調(diào)用python(執(zhí)行py文件)的全過程
- C++通過內(nèi)嵌解釋器調(diào)用Python及間接調(diào)用Python三方庫
- Python 調(diào)用 C++ 傳遞numpy 數(shù)據(jù)詳情
相關文章
C語言函數(shù)棧幀的創(chuàng)建與銷毀原理圖解
我們知道c語言中函數(shù)都是被調(diào)用的,main函數(shù)里面能調(diào)用其他函數(shù),其實main函數(shù)也是被別的函數(shù)調(diào)用的,下面通過本文給大家分享c語言函數(shù)棧幀的創(chuàng)建和銷毀過程,一起看看吧2022-05-05C語言數(shù)據(jù)結(jié)構(gòu)之鏈隊列的基本操作
這篇文章主要為大家介紹了C語言之鏈隊列的基本操作,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助2021-12-12