歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

二分查找真的有你想象中那麼簡單嗎?

  二分查找是查找算法裡家喻戶曉的算法了,其時間復雜度為O(logn),可是如果真的讓你立馬拿出筆寫一個二分查找的函數出來,你確定你可以比較快的完全寫對嗎?

  我們的目的是從一個已經按從小到大的順序排序好的數組arr中查找值為value的元素的位置。

  大體思路我們應該都很清楚:有三個游標,一個low在頭,一個high在尾,還有一個mid指向中間,如果要檢索的數據value比中間的元素arr[mid]小,那麼應該在[low,mid)區間繼續查找,即將high指向mid前面那個元素(也許你可能認為是指向mid元素的位置);如果要檢索的數據value比中間的元素arr[mid]大,那麼應該在(mid,high]區間繼續查找,即將low指向mid後面那個元素(也許你可能認為是指向mid元素的位置)。一直執行這個步驟來縮小搜索區間直到找到arr[k]==value返回k 或 low>high時返回-1表示沒找到。

  其中的細節有很多是需要格外注意的。下面我就通過一個我的一段代碼來引出需要注意的地方。

typedef int DataType;
int binarySearch(const DataType arr[],const DataType value,size_t len)
{
    int low = 0, high = len-1, mid;
    while(low <= high) {
        mid = low + ((high-low)>>1); //思考為什麼不寫作(high+low)/2;
        if(value-arr[mid]<1e-6 && arr[mid]-value<1e-6)//思考為何不寫作arr[mid]!=value
            return mid;
        if(value<arr[mid])
            high = mid-1;    //如果寫作high = mid;可以嗎
        else
            low = mid+1;    //如果寫作low = mid;可以嗎
    }
    return -1;
}

  在看完了上面的代碼後,你有木有想到代碼中注釋部分的問題?當你第一遍寫代碼的時候真的考慮到了嗎,如果沒考慮這些會有什麼過果呢?下面讓我們來一一道來:

  (1)第六行如果寫作mid = (high+low)/2;,有木有發現high+low有點蹊跷?如果你看出來了,恭喜你說明你對數據類型對應的取值范圍很了解!當DataType定義為int型時,兩個int相加,不要以為不會越界哈~另外改成移位操作同樣完成了除以2一樣的效果,但是效率卻提高了。如果用移位的話一定要記得移位運算優先級很低,所以記得加括號!!記得加括號!括號!(重要的事說三遍,哈哈)

  (2)第七行說好的判等呢,為嘛寫成了區間的形式?這個嘛,就要考慮代碼可重用性,因為細心的你可能會發現,傳入的第一個參數是數組類型,什麼類型的數組?這裡暫時定義為int,那如果是float呢?double呢?判等還用==?所以這裡考慮的是普遍情況,通過將兩個數的差值在很小范圍內來表示他們相等,int時照樣適用。

  (3)第10行第12行,才開始寫的時候可能會糾結是不是要減1或者加1,當然還有第五行是寫low <= high還是low < high?舉幾個讓另一種情況出現問題的例子然後你就會明白其中的奧秘了。

  好了,基本上要注意主要的問題就這些了,下面給出一個用模板函數寫好的完整代碼吧!

#include<vector>
#include<iostream>
using namespace std;

//二分查找模板
template<typename T1,typename T2>
int binarySearch(const T1 &arr,const T2 &value,size_t len)
{
    int low = 0, high = len-1, mid;
    while(low <= high) {
        mid = low + ((high-low)>>1); //思考為什麼不寫作(high+low)/2;
        if(value-arr[mid]<1e-6 && arr[mid]-value<1e-6)//思考為何不寫作arr[mid]!=value
            return mid;
        if(value<arr[mid])
            high = mid-1;    //如果寫作high = mid;可以嗎
        else
            low = mid+1;    //如果寫作low = mid;可以嗎
    }
    return -1;
}

int main()
{
    double arr[10];
    int i;
    for(i=0; i<10; i++)
        arr[i] = i;
    for(i=-1; i<11; i++)
        cout<<"the index of '"<<i<<"': "<<binarySearch(arr,i,10)<<endl;

    cout<<endl;
    vector<int> arr_i(arr,arr+10);
    for(i=-1; i<11; i++)
        cout<<"the index of '"<<i<<"': "<<binarySearch(arr_i,i,arr_i.size())<<endl;
    return 0;
}

這個模板函數可以接受不同類型的數組,當然為了兼容C++ STL中的vector容器,又對參數做了小小的改進!

時間倉促,如果內容上有什麼疑問或者錯誤之處,請指出,謝謝!

Golang二分查找算法的簡單實現 http://www.linuxidc.com/Linux/2014-02/96093.htm

二分查找改進版 http://www.linuxidc.com/Linux/2013-10/91721.htm

二分查找的實現及注意事項 http://www.linuxidc.com/Linux/2013-07/87308.htm

用Python實現二分查找 http://www.linuxidc.com/Linux/2012-12/75948.htm

二分查找之Java實現 http://www.linuxidc.com/Linux/2012-05/59869.htm

Java針對數組的普通查找法和二分查找法 http://www.linuxidc.com/Linux/2012-03/57065.htm

Copyright © Linux教程網 All Rights Reserved