概述
1.问题
在一个排好序的数组T[1…n]中查找x，如果x在T中，输出x在T的下标j；如果x不在T中，输出j=0。
2.解析
算法一：遍历检索
数组T为有序（这里假设为升序）数组，因此可通过一次遍历，当T[i] > x时，若仍没有找到x，则说明T数组中不存在x；若遍历发现T[k] == x(k < i)，则输出k。
算法二：二分检索
二分查找是一种效率较高的查找方法，但要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。二分检索可通过不断二分数组从而缩小查找x的区间。
3.设计
算法一：遍历检索
for(i=0；i<数组长度;i++){
判断a[i]是否是所要寻找的数
如果是 就返回位置即i
}
如果遍历完后仍没有找到，就返回0
算法二：二分检索
int binary_search(vectorv,int key)
{
int left=1,right=v.size()-1,mid;
while(left<=right)
{
mid=(left+right)/2;
if(v[mid]<key) left=mid+1;
else if(v[mid]>key) right=mid-1;
else if(v[mid]==key) return mid;
}
return -1;
}
4.分析
遍历检索：从头到尾依次寻找，时间复杂度O(n)
二分检索：不断折半，时间复杂度O(log2(n))
5.源码
[github源码地址]
最后
以上就是无情路灯为你收集整理的检索算法1.问题2.解析3.设计4.分析5.源码的全部内容，希望文章能够帮你解决检索算法1.问题2.解析3.设计4.分析5.源码所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![C++ 字符串（char[]/string）与int型互换；](/uploads/reation/bcimg10.png)
发表评论 取消回复