最近在牛客网刷题,有一道题目是实现二分查找算法,由此便在咖啡店写了段代码,实现这个简单的算法。但同时自己还有一个问题(见最后),希望有朋友能帮忙解答。后期如果自己知道答案,我会自己更新在此。
一. 算法介绍
优点:比较次数少,查找速度快,平均性能好;
缺点:要求待查表为有序表,且插入删除困难。
适用:不经常变动而查找频繁的有序列表。
时间复杂度:o(log(n))
二. 算法代码实现(C++)
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