一、折半查找的定义
折半查找（二分查找）是一种常用的查找算法，它要求待查找的数据结构必须是有序的。
其实现过程如下：
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)的快速查找算法。在数据规模较大的情况下，折半查找算法明显比普通查找算法快许多。但在最坏情况下，它的时间复杂度会失效，这时需要考虑到其他查找算法。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/234007.html
微信扫一扫 
支付宝扫一扫 