【算法】二分查找

最近在牛客网刷题,有一道题目是实现二分查找算法,由此便在咖啡店写了段代码,实现这个简单的算法。但同时自己还有一个问题(见最后),希望有朋友能帮忙解答。后期如果自己知道答案,我会自己更新在此。

一. 算法介绍

   优点:比较次数少,查找速度快,平均性能好;

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

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

   时间复杂度: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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏软件测试经验与教训

Python学习笔记(15)-文件替换

38990
来自专栏编程

数控宏程序的编程及应用

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

21380
来自专栏落影的专栏

Metal入门教程总结

本文介绍Metal和Metal Shader Language,以及Metal和OpenGL ES的差异性,也是实现入门教程的心得总结。

1.2K60
来自专栏王小雷

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

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

235100
来自专栏hbbliyong

使用WPF教你一步一步实现连连看(三)

这次首先对以前的结构进行了调整: 第一步:把MyButton按钮的属性独立成一个类,放在一个单独的MyButton.cs中,把图片的初始化也放到里面。 调整代...

35970
来自专栏数据结构与算法

11:大整数减法

11:大整数减法 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 求两个大的正整数相减的差。 输入共2行,第1行是被减...

296100
来自专栏zhisheng

#每日一题#4

4、已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是() A、head(tail(LS)) B、tail(...

35360
来自专栏从流域到海域

迪杰斯特拉(Dijkstra)算法求图中最短路径

迪杰斯特拉(Dijkstra )算法: 对于图G=(V,E),将图的顶点分为两组: 顶点集S:已求出的最短路径的顶点集合(初始为{v0}); 顶...

24570
来自专栏落影的专栏

iOS开发-OpenGL ES入门教程1

前言 这里是一篇新手教程,环境是Xcode7+OpenGL ES 2.0,目标写一个OpenGL ES的hello world。 OpenGL ES系列教程在...

35290
来自专栏Python绿色通道

数据分析 | Numpy进阶

切片索引Numpy中选取数据子集或者单个元素的方式有很多,一维数组和Pyhon列表的功能差不多,看下图:

14110

扫码关注云+社区

领取腾讯云代金券