C語言算法–有序查找(折半查找/二分查找)

Posted on by

題目

首先我們來把題目瞅一眼：

在一個有序數組中查找具體的某個數字n。
編寫int binary_search (int x, int v[], int n);
功能：在v [0] <= v [1] <= v [2] <= …. <= v [n-1]的數組中查找x.

題目大概的意思就是說這是一串有序的數組，我們編寫代碼完成以下功能：如果輸入的數字在數組中，就輸出找到瞭並輸出下標，如果輸入的數字不在數組中則輸出找不到。

下面看解法：

解法一： 挨個遍歷

#include <stdio.h>
int main()
{
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
    //查找7
    //遍歷 0 ~ sz - 1
    int sz = sizeof(arr) / sizeof(arr[0]);
    int i = 0;
    int flag = 0;//0表示沒有找到
    for (i = 0; i < sz; i++)
    {
        if(7 == arr[i])
        {
            flag = 1;
            break;
        }
    }
    if (1 == flag)
        printf("找到瞭，下標是：%d\n", i);
    else
        printf("沒找到\n");
    return 0;
}

博主這裡的代碼為瞭讓大傢可以看的更清楚，所以沒有寫成輸入的模式，而是直接想要查找7。

這是萬能的方法，就挨個遍歷，有就是有，沒有就是沒有，屬實牛批，但缺點是太費時間，如果要查找1 – 10000000中的10000000，那未免也太久瞭，既然這樣的數組是一串有序的數組，不妨我們可以試試二分查找/折半查找。

方法二：折半查找/二分查找（僅適用於有序查找）

方法分析：

下面分析一下折半查找是怎麼實現的，比如我們的數組是1 – 10，想要查找的數是7，那我們知道下標為0的數組對於1，下標為9的數組對於10，那我們則應該先找到中間下標對應的元素arr[mid]，讓他和7比較，如果比7大，則將最右邊的下標賦值為mid – 1，反之，則將最左邊下標賦值為mid + 1，這樣循環往復無限逼近要查找的數，每次排查一半，直到arr[mid] == 7，就找到瞭，如果直到最左下標和最右下標重合之後都找不到，那這個數一定不在這個有序數組內。

下面我們看代碼是怎麼寫的：

代碼實現：

#include <stdio.h>
int main()
{
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
    //查找7
    //0 ~ sz - 1
    int sz = sizeof (arr) / sizeof (arr[0]);
    int left = 0;
    int right = sz - 1;
    int mid = 0;
    int k = 7;//要查找的元素
    int flag = 0;
    while(left <= right) // 即使是 left == right,也有一個元素需要被查找
    {
        //求中間元素下標
        mid = (left + right) / 2; // 每一次二分查找都要求出新的中間元素下標
        if(arr[mid] < k)
        {
            left = mid + 1;
        }
        else if (arr[mid] > k)
        {
            right = mid - 1;
        }
        else
        {
            //找到瞭
            flag = 1;
            break;
        }
    }
    if (1 == flag)
        printf("找到瞭，下標是：%d\n", mid);
    else
        printf("找不到\n");
    return 0;
}

雖然折半查找看起來代碼比遍歷查找多一些，但其實中間省瞭非常多計算機計算的時間，非常好用~~

總結

本篇文章就到這裡瞭，希望能給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容！

推薦閱讀：