快捷導(dǎo)航

C語言基礎(chǔ)之二分查找知識最全匯總

更新時間：2021年04月29日 14:18:14 作者：峽谷金城武

這篇文章主要介紹了C語言基礎(chǔ)之二分查找知識最全匯總,文中有非常詳細的二分查找基礎(chǔ)知識詳解,對正在學(xué)習(xí)C語言基礎(chǔ)的小伙伴們有非常好的幫助,需要的朋友可以參考下

一、前言

在自學(xué)二分查找的過程中我想到了一些變化問題，有的自己就慢慢理解了，有的在網(wǎng)上找到了答案，奈何沒有找到想要的總結(jié)歸納。我就斗膽自己寫了一篇，號稱史上最全。希望和我一樣的伙伴可以少走一點彎路。

二分查找憑借其低時間復(fù)雜度O(log(n))成為了各個蒟蒻的入門知識，但是其衍生出的各種題目相較原題目而言就沒有那么容易求解，以下借用c語言實現(xiàn)二分查找算法及其衍生。二分查找僅適用于事先已經(jīng)排好序的順序表。其基本思路就是每次取中間數(shù)，如果中間數(shù)大于所求數(shù)就向上查找，反之向下。

二、原始二分查找

1.在有序數(shù)組中尋找一個數(shù)所在下標。

int main(){
    int arr[] = {1,2,3,4,5,6,7,8,9};
    int left,right,fin;
    fin = 3;
    left = 0;right = sizeof(arr)/sizeof(arr[0])-1;
 
    while(left <= right) {
        int mid;
        mid = (left+right) / 2;
        if (arr[mid] == fin) {
            printf("找到了：%d\n", mid);
            return 0;
        }
        if (mid < fin)
            left = mid+1;
        else if (mid > fin)
            right = mid-1;
 
    }
    printf("沒找到");
    return 0;
}

對于這種基本的排序問題，我們通過判斷mid變量與key的大小對有序數(shù)組進行二分。

當(dāng)查找過程中，會出現(xiàn)key值下標坐落在left或right上時的情況，

以下用left舉例

當(dāng)left = key時，一個顯然的結(jié)論，此時arr[mid]無法等于key。其所作工作為減小right，進一步縮進范圍，直到right = left或right = left+1，此時范圍縮小到最小，mid = left。輸出mid的值即為所求下標。

我們當(dāng)然可以在left和right = key時直接輸出key的下標，但是這樣會造成多次比較。

三、二分查找的變化之?dāng)?shù)組元素重復(fù)

對于二分查找而言，會出現(xiàn)數(shù)組元素重復(fù)的情況，以下問題的求解建立在數(shù)組元素重復(fù)的情況下：

1.返回匹配數(shù)key的最小下標

#include <stdio.h>
 
int main() {
    int arr[] = {1,3,3,3,3,4,5,6,7};
    int left,right,lenght,key;
    key = 3;
    left = 0;
    lenght = sizeof(arr)/sizeof(arr[0]);
    right = lenght -1;
    while(left <= right){
        //等于的條件不能忽略
        int mid = (left+right)/2;
        if (arr[mid] < key)
            left = mid + 1;
            //目的是用left來尋找key點，不考慮mid = key的情況
        else
            right = mid - 1;
    }
    if ((left < lenght)&&(arr[left] == key))
        printf("%d\n",left);
    return 0;
}

當(dāng)arr[mid] == key 時，此時直接輸出，則無法達到最小坐標。所以我們需要移動left或right。對于移動left而言，顯然移動后left將大于mid，更不可能找到最小坐標。所以需要移動right，讓left逐漸逼近key的最小下標。

當(dāng)arr[mid] > key時，此時需要移動right，所以此時不會出現(xiàn)left = key的情況

當(dāng)arr[mid] < key時，此時需要移動left，前面已經(jīng)知道m(xù)id<key，當(dāng)left = mid + 1時，（其實類似于單調(diào)函數(shù)的求值）arr[mid] < arr[left] <=key

與原題對比，我們可以發(fā)現(xiàn)，只有arr[mid] == key 時產(chǎn)生了變化，這里有一個顯然的結(jié)論，對于arr[mid] == key ，當(dāng)求最小下標時，我們需要下標left<mid，所以只能移動right，當(dāng)求最大下標時，我們需要right>mid，所以只能移動left。

2.返回匹配數(shù)的最大下標

#include <stdio.h>
 
int main() {
    int arr[] = {1,3,3,3,3,4,5,6,7};
    int left,right,lenght,key;
    key = 3;
    left = 0;
    lenght = sizeof(arr)/sizeof(arr[0]);
    right = lenght -1;
    while(left <= right){
        int mid = (left+right)/2;
        if (arr[mid] <= key)
            left = mid + 1;
        else
            right = mid - 1;
    }
    if ((right >= 0)&&(arr[right] == key))
        printf("%d\n",right);
    return 0;
}

3.返回第一個大于匹配數(shù)的下標

#include <stdio.h>
 
int main() {
    int arr[] = {1,1,1,1,1,4,5,6,7};
    int left,right,lenght,key;
    key = 3;
    left = 0;
    lenght = sizeof(arr)/sizeof(arr[0]);
    right = lenght -1;
    while(left <= right){
        int mid = (left+right)/2;
        if (arr[mid] < key)
            left = mid + 1;
        else
            right = mid - 1;
    }
        printf("%d\n",arr[left]);
    return 0;
}

這個問題，比較簡單，把之前的if條件注釋掉就好了。=_=因為我們在循環(huán)過程中如果沒有找到，left會自己停在第一個大于key的坐標上。

4.查找某個數(shù)的出現(xiàn)次數(shù)

這個問題就比較進階，一開始在一篇介紹二分查找的文章里看到求出現(xiàn)次數(shù)，怎么想也聯(lián)系不到二分查找。最后在網(wǎng)上找到了別人寫的代碼，其實就是兩次二分查找，但是試了好幾次也沒有寫對，看來我的蒟蒻路還有很長。

四、輪轉(zhuǎn)循環(huán)

何為輪轉(zhuǎn)（循環(huán)）有序數(shù)組，就比如說{7，8，9，0，1，2，3，4，5，6}就是一個輪轉(zhuǎn)數(shù)組，其最小值不在[0]點。對于這樣的數(shù)組是否可以使用二分查找，？

對于這種問題，我們需要考慮的是他的順序起點，以{7，8，9，0，1，2，3，4，5，6}為例，他的順序起點為a[3] = 0;

（其實把它理解成為一個分段函數(shù)最容易，但是csdn不好寫數(shù)學(xué)表達式，不好畫圖，有興趣的蒟蒻可以私信我）

#include <stdio.h>
int find(int arr[],int left,int right,int key) {
//傳參a[]是所求數(shù)組，left,right為所求左右下標，key是所求元素
    while (left <= right) {
        int mid = (left + right) / 2;
        if(arr[mid] > key){
            if(arr[mid] < arr[right])//當(dāng)此式成立時表明元素順序起點在mid左邊。
                right = mid - 1;
            else {//元素順序起點在mid右邊，但是key有可能在mid左邊有可能在mid右邊
                if (key > arr[left])//在左邊
                    right = mid - 1;
                else
                    left = mid + 1;
            }
        }
        else if(arr[mid] < key){
            if(arr[mid] > arr[left])//在mid左邊是遞增的（順序起點在[0]或右邊）
                left = mid + 1;
            else{//順序起點在左邊且不在[0]上
                if (key > arr[right])//在mid左邊
                    right = mid - 1;
                else
                    left = left + 1;
            }
        }
        else//當(dāng)相等時直接返回mid
           return mid;
 
    }
 
}
int main() {
    int left,right,key,mid;
    int arr[] = {7,8,9,0,1,2,3,4,5,6};
    left = 0;
    right =( sizeof(arr)/sizeof(arr[0]) ) - 1;
    key = 4;
    mid = find(arr,left,right,key);
    printf("峽谷吳彥祖 %d",mid);
    return 0;
}

五、楊氏矩陣

在劍指offer的項目練習(xí)上，有在楊氏矩陣中對一個數(shù)進行查找的案例。題中所給出的解題思路是利用楊氏矩陣每行遞增，每列遞增的性質(zhì)每次排除某行或某列。而在我的實踐過程中，其可以采用二分查找的思路，對大規(guī)模的矩陣進行更加優(yōu)化的查找。以下是此方法的代碼：

int yang_matrix_2(int arr[X][Y],int num) {
    int x = 0;
    int y = Y;
    int a = x;
    int b = y;
    do{
       a = x;b = y;
        if (arr[x][y] > num) {//在列上進行折半查找
            int left = 0;
            int right = Y-1;
            while (left <= right){
                int mid = (((left ^ right) >> 1)+(left & right));
                if (arr[x][mid] > num)
                    right = mid - 1;
                else {
                    if (arr[x][mid] < num)
                        left = mid + 1;
                    else
                        return 1;}
            }
            y = left;
            x--;
        }
        else{
            if(arr[x][y] < num){
                int left = 0;
                int right = X-1;
                while (left <= right){
                    int mid = (((left ^ right) >> 1)+(left & right));
                    if (arr[mid][y] > num)
                        right = mid - 1;
                    else {if (arr[mid][y] < num)
                            left = mid + 1;
                        else
                            return 1;}
                }
                x = right;
                ++y;
            }//在行上進行折半查找
            else
                return 1;
        }
    }while ((x != a) && (y != b));
    return 0;
}