快捷導(dǎo)航

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

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

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

題目

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

在一個(gè)有序數(shù)組中查找具體的某個(gè)數(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ù)組中，就輸出找到了并輸出下標(biāo)，如果輸入的數(shù)字不在數(shù)組中則輸出找不到。

下面看解法：

解法一：挨個(gè)遍歷

#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("找到了，下標(biāo)是：%d\n", i);
    else
        printf("沒找到\n");
    return 0;
}

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

這是萬能的方法，就挨個(gè)遍歷，有就是有，沒有就是沒有，屬實(shí)牛批，但缺點(diǎn)是太費(fèi)時(shí)間，如果要查找1 - 10000000中的10000000，那未免也太久了，既然這樣的數(shù)組是一串有序的數(shù)組，不妨我們可以試試二分查找/折半查找。

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

方法分析：

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

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

代碼實(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,也有一個(gè)元素需要被查找
    {
        //求中間元素下標(biāo)
        mid = (left + right) / 2; // 每一次二分查找都要求出新的中間元素下標(biāo)
        if(arr[mid] < k)
        {
            left = mid + 1;
        }
        else if (arr[mid] > k)
        {
            right = mid - 1;
        }
        else
        {
            //找到了
            flag = 1;
            break;
        }
    }
    if (1 == flag)
        printf("找到了，下標(biāo)是：%d\n", mid);
    else
        printf("找不到\n");
    return 0;
}

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