本文将介绍二分查找的递归形式与非递归形式，并对临界情况进行分析
二分查找基本思想
基本思想：在有序的数组中（不适用于链表）取中间元素为比较对象，如果要查找的值比中间元素的值小，到中间元素的左边去查，如果要查找的值比中间元素的值大，到中间元素的右边去查，如果相等则查找成功，不断重复此过程。
二分查找非递归代码
searchHelper.h辅助代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 生成有序的数组 n:数据个数 [0,n)
int * generateOrderArray(int n)
{
int i;
int *arr = NULL;
if (n > 0 )
{
arr = (int *) malloc(sizeof(int) * n);
for (i = 0; i < n; ++i)
{
arr[i] = i;
}
}
return arr;
}
// 打印数组内容
void printArray(int * arr, int n)
{
int i;
for (i = 0; i < n; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
}
// 测试该算法
void testSearch(char * searchName, int (*search)(int *, int , int ), int * arr, int n )
{
int i;
clock_t startTime = clock();
for (i = 0; i < n; ++i)
{
if (i != search(arr, n, i))
{
printf("no found %d\n", i);
}
}
clock_t endTime = clock();
printf("%s test complete. cost time: %lf s\n", searchName, (double)(endTime - startTime) / CLOCKS_PER_SEC);
}
边界范围[left,right],BinarySearch1.c如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 定义二分查找的区间为 [left, right]
int binarySearch1(int *arr, int n, int target)
{
int left = 0, right = n - 1; // 在[left...right]的范围里寻找target
while (left <= right) // 当 left == right时,区间[left...right]依然是有效的
{
// int mid = (left + right) / 2; 此写法有bug 如果left + right超出了整数的范围 数据溢出
int mid = left + (right - left) / 2;
if (arr[mid] == target)
{
return mid;
} else if (arr[mid] > target)
{
right = mid - 1;
} else{
left = mid + 1;
}
}
return -1; // 找不到
}
int main(void)
{
int n = pow(10, 7);
int *arr1 = generateOrderArray(n);
testSearch("BinarySearch1", binarySearch1, arr1, n);
return 0;
}
边界范围[left,right),BinarySearch2.c如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 在binarySearch1的基础上 更改 二分查找的区间为 [left, right)
int binarySearch2(int *arr, int n, int target)
{
int left = 0, right = n; // 在[left...right)的范围里寻找target
while (left < right) // 当 left < right时,区间[left...right)依然是有效的
{
// int mid = (left + right) / 2; 此写法有bug 如果left + right超出了整数的范围 数据溢出
int mid = left + (right - left) / 2;
if (arr[mid] == target)
{
return mid;
} else if (arr[mid] > target)
{
right = mid; // 从mid -1 改成mid
} else{
left = mid + 1;
}
}
return -1; // 找不到
}
int main(void)
{
int n = pow(10, 7);
int *arr2 = generateOrderArray(n);
testSearch("BinarySearch2", binarySearch2, arr2, n);
return 0;
}
二分查找递归
边界范围[left,right],BinarySearchRecursive.c如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 定义二分查找的区间为 [left, right]
int __BinarySearchRecursive(int *arr, int left,int right, int target)
{
if (left > right) // 根据定义的区间[left, right] 当left == right时 还有效
{
return -1;
}
int mid = (right - left) / 2 + left;
if (arr[mid] == target)
{
return mid;
} else if (arr[mid] < target)
{
return __BinarySearchRecursive(arr, mid + 1, right,target);
} else
{
return __BinarySearchRecursive(arr, left, mid - 1, target);
}
}
// 统一接口
int BinarySearchRecursive(int *arr, int n, int target)
{
return __BinarySearchRecursive(arr, 0, n - 1, target);
}
int main(void)
{
int n = pow(10, 7);
int *arr3 = generateOrderArray(n);
testSearch("BinarySearchRecursive", BinarySearchRecursive, arr3, n);
return 0;
}
总结
将BinarySearch1.c BinarySearch2.c BinarySearchRecursive.c 分别改成.h，在Main.c中比较三者运行效率,二分查找[0,n)之间的所有元素 Main.c如下：
int main(void)
{
int n = pow(10, 7);
int *arr1 = generateOrderArray(n);
int *arr2 = generateOrderArray(n);
int *arr3 = generateOrderArray(n);
testSearch("BinarySearch1", binarySearch1, arr1, n);
testSearch("BinarySearch2", binarySearch2, arr2, n);
testSearch("BinarySearchRecursive", BinarySearchRecursive, arr3, n);
return 0;
}
Clion运行结果如下：
二分查找缺点：
- 必须按关键字排序，有时排序也很费时。
- 只适用于顺序存储结构，所以插入、删除操作需大量移动元素
二分查找适用于一经建立就很少改动，而又经常需要查找的线性表。对于那些经常需要改动的线性表，可以采用链表存储结构，进行顺序查找
可以看出递归形式与非递归形式相比的较慢 相关源码下载