【算法】二分查找

优点：比较次数少，查找速度快，平均性能好；

缺点：要求待查表为有序表，且插入删除困难。

适用：不经常变动而查找频繁的有序列表。

时间复杂度：o(log(n))

``` 1 // BinarySearch.cpp : Defines the entry point for the console application.
2
3 #include "stdafx.h"
4 #include <iostream>
5
6 using namespace std;
7
8 //compare function
9 int compare(const void *val1, const void *val2)
10 {
11     int iVal1 = *(int*)val1;
12     int iVal2 = *(int*)val2;
13
14     cout << "Compare: " << iVal1 << ", " << iVal2 << endl;
15
16     if (iVal1 > iVal2)
17     {
18         return 1;
19     }
20     else if (iVal1 == iVal2)
21     {
22         return 0;
23     }
24     else
25     {
26         return -1;
27     }
28 }
29
30 //nel: num of element, width: every element size
31 void *bsearch(const void *key, const void *base, size_t nel, size_t width, int (*compar)(const void*, const void *))
32 {
33     int pos = nel / 2;
34
35     cout << "Position: " << pos << endl;
36
37     int result = (*compar)(key, (int *)base + pos);
38
39     if (pos == 0)
40     {
41         return result == 0 ? (void *)base : NULL;
42     }
43
44     if (result > 0)
45     {
46         return bsearch(key, (int *)base + pos + 1, pos, width, compar);
47     }
48     else if (result == 0)
49     {
50         return (void *)base;
51     }
52     else
53     {
54         return bsearch(key, base, pos, width, compar);
55     }
56 }
57
58 int _tmain(int argc, _TCHAR* argv[])
59 {
60     int array[] = { 1, 3, 5, 6, 11, 13, 17, 29, 44, 66, 79, 99, 111 };
61     int arrayNum = sizeof(array) / sizeof(*array);
62     cout << "Array Element Num: " << arrayNum << endl;
63
64     int searchVal = 13;
65     cout << "Search Value: " << searchVal << endl;
66
67     int *result = (int *)bsearch(&searchVal, array, arrayNum, sizeof(*array), compare);
68
69     cout << "Result: " << (result == NULL ? "Not Found" : "Found") << endl;
70
71     system("pause");
72     return 0;
73 }```

这里自己有一个小问题，就是算法接口中的size_t width参数我并没有用到，同时我假设元素都是INT型。请问这里该如何修改，既能用到width，又不用假设元素为特定类型？谢谢。

Best Regards

Kevin Song

0 条评论

相关文章

38990

数控宏程序的编程及应用

1. 什么场合会用到宏程序编程？ 其实说起来宏就是用公式来加工零件，比如说椭圆，如果没有宏的话，我们要逐点算出曲线上的点，然后慢慢来用直线逼近，如果是个光洁度要...

21380

1.2K60

SAS学习笔记之《SAS编程与数据挖掘商业案例》（3）变量操作、观测值操作、SAS数据集管理

SAS学习笔记之《SAS编程与数据挖掘商业案例》（3）变量操作、观测值操作、SAS数据集管理 1. SAS变量操作的常用语句 ASSIGNMENT 创建或修改...

235100

35970

24570

35290

14110