高效算法——二分查找

今天又get到了好多新知識，和大家share一下吧。

折半查找

比如我買了一雙鞋，你好奇問我多少錢，我說不超過300元。你還是好奇，你想知道到底多少，我就讓你猜，你會 怎麼猜？

答案：你每次猜中間數。

對吧，是以我們一般猜數字的時候都從中間猜，再根據大了或者小了調整。應用到算法上其實省去了好多麻煩，直接将查找範圍縮小了将近一半，大大提高了運算效率。顧此算法非常高效，以下可供大家了解一下：

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int k = 7;

    int left = 0;
    int right = sizeof(arr)/sizeof(arr[0])- 1;
    int mid = 0; 

    while (left <= right)
    {
        mid = left + (right - left) / 2;
        if (arr[mid] < k)
        {
            left = mid + 1;
        }   
        else if (arr[mid]>k)
        {
            right = mid - 1;
        }
        else
        {
            printf("找到了，下标是：%d\n",mid);
            break;
        }
    }
    if (left > right)
        printf("找不到了\n");
    system("pause");
    return 0;
}           

這個是一個簡單的查找數組元素的方法，當然後續小洛會繼續拓展，比如你輸一個數組，再次查找你剛才所輸入元素的下标，将再次進行代碼優化。當然我們也可以将其設定為函數，更加友善我們調用。以下為函數模型：

int binary_search(int arr[], int k, int sz)
{
    int left = 0;
    int mid = 0;
    int right = sz - 1;

    while (left <= right)
    {
        mid = left + (right - left) / 2;
        if (arr[mid] < k)
        {
            left = mid + 1;
        }
        else if (arr[mid]>k)
        {
            right = mid - 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}           

int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int k = 7;
    int sz = sizeof(arr) / sizeof(arr[0]) - 1;
    int ret = binary_search(arr,k ,sz);
    if (ret == -1)
    {
        printf("找不到呀!\n");
    }
    else
    {
        printf("找到了，下标是：%d", ret);
    }

    system("pause");
    return 0;

}           

int binary_search(int arr[], int k, int left,int right)
{
    int mid = 0;

    while (left <= right)
    {
        mid = left + (right - left) / 2;
        if (arr[mid] < k)
        {
            left = mid + 1;
        }
        else if (arr[mid]>k)
        {
            right = mid - 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}