欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

c++與python實(shí)現(xiàn)二分查找的原理及實(shí)現(xiàn)

 更新時(shí)間:2022年03月11日 09:06:28   作者:機(jī)器學(xué)習(xí)入坑者  
本文介紹了c++與python實(shí)現(xiàn)二分查找的原理及實(shí)現(xiàn),二分查找指首先將數(shù)組中間值和目標(biāo)值進(jìn)行比較,如果相等則返回;如果不相等,則選擇中間值左邊的一半或者右邊的一半進(jìn)行比較;不斷重復(fù)直到檢索完畢,下文相關(guān)資料需要的朋友可以參考一下

在計(jì)算機(jī)中,數(shù)據(jù)的查找方式與其存儲(chǔ)方式關(guān)系密切。試想一下,如果圖書館中書籍雜亂無章的存放,那么要想找到心儀的書籍將會(huì)非常困難。為此,人們常常將物品按照某種規(guī)則或次序進(jìn)行放置,目的是便于日后的查找。

作為查找算法家族中的一員,二分查找正是利用數(shù)據(jù)按次序存儲(chǔ)這一優(yōu)點(diǎn),極大的提升了查找目標(biāo)值所在位置的速度。

二分查找的核心思想是:首先將數(shù)組中間值和目標(biāo)值進(jìn)行比較,如果相等則返回;如果不相等,則選擇中間值左邊的一半或者右邊的一半進(jìn)行比較;不斷重復(fù)直到檢索完畢。首先來看下面這個(gè)gif,其中藍(lán)色圈表示左位置,粉色圈表示右位置,綠色圈表示中間位置:

首先定義的是左邊界(藍(lán)色圈)和右邊界(粉色圈),進(jìn)而根據(jù)左邊界和右邊界計(jì)算出中間位置(綠色圈);然后,比較中間位置的值和目標(biāo)值的大小,比較結(jié)果包含3種情況

  • 如果相等則表示查找成功,返回中間位置;
  • 如果中間位置的值小于目標(biāo)值,則說明目標(biāo)值在中間位置到右邊界這一半;
  • 如果中間位置的值大于目標(biāo)值,則說明目標(biāo)值在左邊界到中間位置這一半;

上述步驟的循環(huán)需要終止條件,即左邊界小于或等于右邊界,表明此時(shí)已經(jīng)搜索完成,目標(biāo)數(shù)值不在數(shù)據(jù)中存在。

1、時(shí)間復(fù)雜度與優(yōu)缺點(diǎn)

既然每次搜索后區(qū)間長(zhǎng)度都減半,假設(shè)數(shù)據(jù)個(gè)數(shù)(即區(qū)間長(zhǎng)度)為n,那么算法每次迭代得到的區(qū)間長(zhǎng)度依次為n/2,n/4,n/8等等,其通項(xiàng)如下,k表示循環(huán)次數(shù):

最壞的情況,就是搜索到區(qū)間長(zhǎng)度為1,即最后只剩1個(gè)元素:

 

所以,可以求得最壞情況下需要運(yùn)行的次數(shù)為:

因此二分查找復(fù)雜度為O(logn),相比于順序查找其速度獲得了極大的提高(優(yōu)點(diǎn))。但是,必須注意二分查找需要保證數(shù)據(jù)是有序的,這就要求數(shù)據(jù)必須預(yù)先進(jìn)行排序(缺點(diǎn))。

2、python實(shí)現(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:
? ? ? ? # 中間位置計(jì)算
? ? ? ? mid = int((left+right)/2)
? ? ? ? if ordered_list[mid] == target_value:
? ? ? ? ? ? return "index is {}, target value is {}".format(mid, ordered_list[mid])
? ? ? ? # 此時(shí)目標(biāo)值在中間值右邊,更新左位置
? ? ? ? elif ordered_list[mid] < target_value:
? ? ? ? ? ? left = mid + 1
? ? ? ? # 此時(shí)目標(biāo)值在中間值左邊,更新右位置
? ? ? ? elif ordered_list[mid] > target_value:
? ? ? ? ? ? right = mid - 1
? ? # 搜索結(jié)束沒有找到
? ? return "Not find"

3、C++實(shí)現(xiàn)

int binarySearch(int *orderedData, int dataLength, int targetValue) {
?? ?int left = 0;
?? ?int right = dataLength - 1;
?? ?int mid;
?? ?// 終止條件
?? ?while (left<=right)
?? ?{
?? ??? ?// 中間位置計(jì)算
?? ??? ?mid = (left + right) / 2;
?? ??? ?if (*(orderedData + mid) == targetValue) {
?? ??? ??? ?return mid;
?? ??? ?}
?? ??? ?// 目標(biāo)值在中間值右邊,更新左位置
?? ??? ?else if (*(orderedData + mid) < targetValue){
?? ??? ??? ?left = mid + 1;
?? ??? ?}
?? ??? ?// 目標(biāo)值在中間值左邊,更新右位置
?? ??? ?else
?? ??? ?{
?? ??? ??? ?right = mid - 1;
?? ??? ?}
?? ?}
?? ?// 搜索不到,返回-1
?? ?return -1;
}

到此這篇關(guān)于c++與python實(shí)現(xiàn)二分查找的原理及實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)c++與python實(shí)現(xiàn)二分查找內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C++基礎(chǔ)學(xué)習(xí)之函數(shù)重載的簡(jiǎn)單介紹

    C++基礎(chǔ)學(xué)習(xí)之函數(shù)重載的簡(jiǎn)單介紹

    函數(shù)重載是一種特殊情況,C++允許在同一作用域中聲明幾個(gè)類似的同名函數(shù),這些同名函數(shù)的形參列表(參數(shù)個(gè)數(shù),類型,順序)必須不同,常用來處理實(shí)現(xiàn)功能類似數(shù)據(jù)類型不同的問題。這篇文章主要給大家介紹了關(guān)于C++基礎(chǔ)學(xué)習(xí)之函數(shù)重載的相關(guān)資料,需要的朋友可以參考下
    2019-01-01
  • C++中純虛函數(shù)的實(shí)例詳解

    C++中純虛函數(shù)的實(shí)例詳解

    純虛函數(shù)就是一個(gè)在基類中的虛函數(shù),差別只是在一般的虛函數(shù)聲明的后面加了“=0”,下面這篇文章主要給大家介紹了關(guān)于C++中純虛函數(shù)的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2022-06-06
  • C語言實(shí)現(xiàn)貪吃蛇游戲代碼

    C語言實(shí)現(xiàn)貪吃蛇游戲代碼

    大家好,本篇文章主要講的是C語言實(shí)現(xiàn)貪吃蛇游戲代碼,感興趣的同學(xué)趕快來看一看吧,對(duì)你有幫助的話記得收藏一下
    2022-02-02
  • C++中std::is_object的具體使用

    C++中std::is_object的具體使用

    std::is_object是一種C++類型特性,其用途是判斷一個(gè)類型是否是一個(gè)對(duì)象類型,本文主要介紹了C++中std::is_object的具體使用,感興趣的可以了解一下
    2024-01-01
  • C語言函數(shù)棧幀的創(chuàng)建與銷毀原理圖解

    C語言函數(shù)棧幀的創(chuàng)建與銷毀原理圖解

    我們知道c語言中函數(shù)都是被調(diào)用的,main函數(shù)里面能調(diào)用其他函數(shù),其實(shí)main函數(shù)也是被別的函數(shù)調(diào)用的,下面通過本文給大家分享c語言函數(shù)棧幀的創(chuàng)建和銷毀過程,一起看看吧
    2022-05-05
  • C++使用遞歸函數(shù)和棧操作逆序一個(gè)棧的算法示例

    C++使用遞歸函數(shù)和棧操作逆序一個(gè)棧的算法示例

    這篇文章主要介紹了C++使用遞歸函數(shù)和棧操作逆序一個(gè)棧的算法,結(jié)合實(shí)例形式分析了C++遞歸函數(shù)與逆序棧的相關(guān)操作技巧,需要的朋友可以參考下
    2017-05-05
  • C++實(shí)現(xiàn)播放音頻的示例詳解

    C++實(shí)現(xiàn)播放音頻的示例詳解

    這篇文章主要為大家詳細(xì)介紹了C++如何利用第三方庫實(shí)現(xiàn)播放音頻的功能,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2024-01-01
  • C語言數(shù)據(jù)結(jié)構(gòu)之鏈隊(duì)列的基本操作

    C語言數(shù)據(jù)結(jié)構(gòu)之鏈隊(duì)列的基本操作

    這篇文章主要為大家介紹了C語言之鏈隊(duì)列的基本操作,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2021-12-12
  • C/C++ 凸多邊形求對(duì)角線交點(diǎn)的示例代碼

    C/C++ 凸多邊形求對(duì)角線交點(diǎn)的示例代碼

    這篇文章主要介紹了C/C++ 凸多邊形求對(duì)角線交點(diǎn)的示例代碼,代碼簡(jiǎn)單易懂,對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2020-11-11
  • C語言中scanf與scnaf_s函數(shù)詳解

    C語言中scanf與scnaf_s函數(shù)詳解

    大家好,本篇文章主要講的是C語言中scanf與scnaf_s函數(shù)詳解,感興趣的同學(xué)趕快來看一看吧,對(duì)你有幫助的話記得收藏一下
    2022-01-01

最新評(píng)論