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

作為查找算法家族中的一員，二分查找正是利用數(shù)據(jù)按次序存儲這一優(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ū)間長度都減半，假設(shè)數(shù)據(jù)個(gè)數(shù)（即區(qū)間長度）為n，那么算法每次迭代得到的區(qū)間長度依次為n/2，n/4，n/8等等，其通項(xiàng)如下，k表示循環(huán)次數(shù)：

最壞的情況，就是搜索到區(qū)間長度為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)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論