浅析折半查找的时间复杂度

一、折半查找的定义

折半查找（二分查找）是一种常用的查找算法，它要求待查找的数据结构必须是有序的。

其实现过程如下：

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)的快速查找算法。在数据规模较大的情况下，折半查找算法明显比普通查找算法快许多。但在最坏情况下，它的时间复杂度会失效，这时需要考虑到其他查找算法。