C語言算法的折半查找或二分查找怎么用

本篇內(nèi)容介紹了“C語言算法的折半查找或二分查找怎么用”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

目錄

• 題目

• 解法一： 挨個遍歷

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

  
  

題目

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

在一個有序數(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ù)組中，就輸出找到了并輸出下標(biāo)，如果輸入的數(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("找到了，下標(biāo)是：%d\n", i);
    else
        printf("沒找到\n");
    return 0;
}

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

這是萬能的方法，就挨個遍歷，有就是有，沒有就是沒有，屬實牛批，但缺點是太費(fèi)時間，如果要查找1 - 10000000中的10000000，那未免也太久了，既然這樣的數(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)重合之后都找不到，那這個數(shù)一定不在這個有序數(shù)組內(nèi)。

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

代碼實現(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,也有一個元素需要被查找
    {
        //求中間元素下標(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;
}

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

“C語言算法的折半查找或二分查找怎么用”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！