顺序搜索Programmer每天都碰到顺序搜索,其code snippet:
/*
* 顺序遍历数组,搜索v值是否存在。如果存在,返回相应的位置索引,
* 否则返回-1
*/
int sequentialSearch(int a[],int v,int l,int r){
int i;
for(i = l;i <= r;i++){
if(v == a[i])
return i;
}
return -1;
}
分析:
- 假设数组拥有N个元素,对于不成功的搜索,总是搜索N个元素;对于成功的搜索,平均搜索次数为N/2。
- 假设每个数组元素被搜索到的概率相等,那么平均搜索次数可以这样计算:(1+2+...+N)/N = (N+1)/2
- 对于排序数组,相关性质不变。
二分搜索code snippet:
/*
* 二分搜索,非递归实现
* 假设:数组元素已经按序排列
*/
int binarySearch(int a[],int v,int l,int r){
int m;
while(l<=r){
m = (l+r)/2;
if(v == a[m])
return m;
if(v > a[m]){
l = m + 1;
}else{
r = m - 1;
}
}
return -1;
}
/*
* 二分搜索,递归实现
*/
//dataForExperiment数组定义及初始化
int binarySearch(int v,int l,int r){
if(l > r){
return -1;
}
int m = (l + r)/2;
if(v == dataForExperiment[m]){
return m;
}else{
if(v > dataForExperiment[m]){
return binarySearch(v,m+1,r);
}else{
return binarySearch(v,l,m-1);
}
}
}
分析:
- 假设Tn表示在最坏情况下二分搜索需要比较的次数,那么有Tn=Tn/2+1,其中n>=2,T1=1
- 求解递归式,可以得到二分搜索检查元素个数永远不超过lgn+1。
- 数组必须是已经排好序的。
分享到:
相关推荐
顺序和二分查找 课程设计 数组顺序查找 链表顺序查找 C语言编程
算法-数据结构和算法-3-顺序表.rar
数据结构-基本算法-顺序栈(学生时代源码,调试可运行)
北京工业大学--算法作业2--动态规划算法实现0-1背包问题---Java代码 利用动态规划算法实现0-1背包问题或装配线调度问题。(二选一) 要求测试数据以文本文件的形式存储, 即所有的数据由文本文件读入。 利用动态...
基本算法---计数.sb3
算法分析与设计-实验二 二分查找实验报告
算法初步课件 1.2.3 基本算法语句--循环语句.ppt
算法初步课件 1.2.2 基本算法语句--条件语句.ppt
算法-数据结构和算法-15-二分查找.rar
数据结构-查找算法 二分查找 二叉顺序数 哈希查找
基本算法语句--赋值、输入、输出语句.doc
算法-搜索- 启发式搜索- 爬山法.rar
Bellman-Ford算法与差分约束系统
最常用的二分搜索变体由 Hermann Bottenbruch 于 1962 年首次发布,此后没有明显变化。下面我将描述几个具有改进性能的新变体。最值得注意的变体是单向二分搜索,它在小于 100 万个 32 位整数的数组上的执行速度比...
数据结构,算法与应用 ---C++语言描述(代码与习题答案)数据结构,算法与应用 ---C++语言描述(代码与习题答案)
《计算机算法设计与分析》王晓东编著 算法实现题2-1
查找算法:二分查找、顺序查找的实现 参见博客:http://blog.csdn.net/xiaowei_cqu/article/details/7748260
算法-理论基础- 线性表- 顺序表(包含源程序).rar
算法-理论基础- 查找- 顺序查找(包含源程序).rar
算法-理论基础- 栈- 顺序栈(包含源程序).rar