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

更新時間：2021年08月24日 14:56:26 作者：Aaronskr

我們知道無序查找只能靠遍歷，如果有序查找我們還挨個去遍歷，未免太浪費時間，所以這里我們會用到不一樣的方法，希望能給你帶來幫助

題目

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

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

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

下面看解法：

解法一：挨個遍歷

#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，那未免也太久了，既然這樣的數(shù)組是一串有序的數(shù)組，不妨我們可以試試二分查找/折半查找。

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

方法分析：

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

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

代碼實現(xiàn)：

#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;
}

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