二分查找
二分查找算法,也叫折半查找算法。时间复杂度为 O(logn),只适用于有序表。
#include <stdio.h>
// 循环实现方式
int binary_search(int *a, int n, int key)
{
int low, high, mid;
low = 0;
high = n - 1;
while (low <= high) {
mid = low + (high - low) / 2; // = (low + high) / 2
if (key < a[mid]) {
high = mid - 1;
} else if (key > a[mid]) {
low = mid + 1;
} else {
return mid; // mid 即为查找到的位置
}
}
}
// 递归实现方式
int binary_search_internally(int *a, int low, int high, int key); // 函数声明
int binary_search_2(int *a, int n, int key)
{
return binary_search_internally(a, 0, n - 1, key);
}
int binary_search_internally(int *a, int low, int high, int key)
{
if (low > high) return -1;
int mid = low + (high - low) / 2;
if (key < a[mid])
return binary_search_internally(a, low, mid - 1, key);
else if (key > a[mid])
return binary_search_internally(a, mid + 1, high, key);
else
return mid;
}
int main()
{
int a[10] = {1, 16, 24, 35, 47, 59, 62, 73, 88, 99};
int len = sizeof(a) / sizeof(int); // 求数组的长度
//printf("%d\n", binary_search(a, len, 59));
printf("%d\n", binary_search_2(a, len, 59));
return 0;
}