淺析折半查找的時間複雜度

一、折半查找的定義

折半查找（二分查找）是一種常用的查找演算法，它要求待查找的數據結構必須是有序的。

其實現過程如下：

int binary_search(int arr[], int left, int right, int target)
{
    while(left <= right)
    {
        int mid = (left + right) / 2;
        if(arr[mid] == target)
            return mid;
        if(arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

二、折半查找的時間複雜度與時間複雜度分析

常見的演算法時間複雜度分別有O(1), O(logn), O(n), O(nlogn), O(n²), O(n³)等。

而折半查找的時間複雜度為O(logn)，也就是說它屬於時間複雜度比較小的演算法，適用於大數據量的快速查找。

下面從多個方面來詳細闡述折半查找的時間複雜度。

三、折半查找的時間複雜度與數據規模

折半查找的時間複雜度與數據規模有關，具體表現為：

當數據規模n增大時，時間複雜度O(logn)的速度要比O(n)快，因為O(logn)的增長速度是比O(n)慢的。

如下面的示例所示，隨著數據規模的增大，折半查找演算法與普通查找演算法的時間複雜度對比：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int search(int arr[], int len, int target)
{
    for(int i = 0; i < len; i++)
    {
        if(arr[i] == target)
            return i;
    }
    return -1;
}

int binary_search(int arr[], int left, int right, int target)
{
    while(left <= right)
    {
        int mid = (left + right) / 2;
        if(arr[mid] == target)
            return mid;
        if(arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

int main()
{
    int len = 100000000;
    int* arr = (int*)malloc(len * sizeof(int));
    for(int i = 0; i < len; i++)
        arr[i] = i;
    int target = len - 1;
    clock_t start, end;
    int ret;

    start = clock();
    ret = binary_search(arr, 0, len - 1, target);
    end = clock();
    printf("binary_search: %d, time: %fs\n", ret, (double)(end - start) / CLOCKS_PER_SEC);

    start = clock();
    ret = search(arr, len, target);
    end = clock();
    printf("search: %d, time: %fs\n", ret, (double)(end - start) / CLOCKS_PER_SEC);

    free(arr);
    return 0;
}

當數據規模為100000000時，折半查找演算法的耗時只有0.001秒，而普通查找演算法的耗時卻為4.737秒。

四、折半查找的時間複雜度與查找時間

在平均時間複雜度為O(logn)的前提下，折半查找演算法的查找時間比較快，因為它每次可以將查找範圍縮小為原來的一半。

而在最壞情況下，折半查找的時間複雜度O(logn)也會失效，比如當查找的關鍵字不在序列中時，折半查找會一直循環到我查找範圍為空，這時它的時間複雜度將達到O(n)。

下面的示常式序中，為了讓折半查找失效，我將查找目標設置為0xFFFFFFF（因為序列中最大的數為0x7FFFFFFF，所以它不可能在序列中）：

int binary_search(int arr[], int left, int right, int target)
{
    while(left <= right)
    {
        int mid = (left + right) / 2;
        if(arr[mid] == target)
            return mid;
        if(arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

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

    ret = binary_search(arr, 0, 9, 0xFFFFFFF);
    printf("%d\n", ret);

    return 0;
}

程序會輸出-1，表示查找目標不在序列中。由於這個查找目標不在序列中，折半查找演算法的每次循環都會掃描整個序列，這時時間複雜度會退化為O(n)。

總結

綜上所述，折半查找演算法是一種時間複雜度為O(logn)的快速查找演算法。在數據規模較大的情況下，折半查找演算法明顯比普通查找演算法快許多。但在最壞情況下，它的時間複雜度會失效，這時需要考慮到其他查找演算法。