首页 > 代码库 > 【算法】二分查找
【算法】二分查找
最近在牛客网刷题，有一道题目是实现二分查找算法，由此便在咖啡店写了段代码，实现这个简单的算法。但同时自己还有一个问题（见最后），希望有朋友能帮忙解答。后期如果自己知道答案，我会自己更新在此。
一. 算法介绍
优点：比较次数少，查找速度快，平均性能好；
缺点：要求待查表为有序表，且插入删除困难。
适用：不经常变动而查找频繁的有序列表。
时间复杂度：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 else25 {26 return -1;27 }28 }29 30 //nel: num of element, width: every element size31 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 else53 {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
【算法】二分查找
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。