算法分析与设计作业3

本文主要是介绍算法分析与设计作业3，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1.问题
写出两种检索算法：在一个排好序的数组T[1…n]中查找x，如果x在T中，输出x在
T的下标j；如果x不在T中，输出j=0.按实验模板编写，“分析”部分仅给出复杂度
结果即可。
2.解析
顺序查找：这是最简单也是最先想到的算法，但是它的缺陷也很明显，如果要找到的数在数组的末尾，那么要找到这个数就必须遍历一遍数组，当这个数组很大时，找到这个数所要花费的时间是我们无法接受的。
二分查找：相较于顺序查找，二分查找是我们所学过的较为快速的一种查找方式，它的操作步骤也很简单，首先将这个数组分为两部分，取一个中间值与要查找的值相比较，如果比要查找的值值大那就在左半边查找，反之则在右半边查找。
3.设计
1.顺序查找：

int SequentialSearch(int T[], int n, int x)//传递过来数组的第一个值的地址
{
int i;
for (i = 0; i < n; i++)//从0开始遍历一遍数组
{
if (T[i] == x)return i;//找到就输出下标
}
return 0;//没找到就输出0
}
2.二分查找

int BinarySearch(int T[], int n, int x)
{
int low = 0;
int high = n-1;
int middle;
while (low <= high)//设置跳出条件，当查找的最小边界大于最大边界时就跳出
{
middle = (low + high) / 2; //找出中间值
if (x < T[middle])high = middle - 1; //向中间值的左半边查找
else if (x > T[middle])low = middle + 1; //向中间值的右半边查找
else return middle; //找到就返回下表
}
return 0;//没找到就输出0
}
4.分析
1.顺序查找：因为是从头到尾遍历一遍，所以查找的时间复杂度跟数组的个数有关，所以时间复杂度为O(n).
2.二分查找：因为是不断地折中查找，所以时间复杂度为O(logn).

5.源码
https://github.com/jinwanzaodianshui/zuoye3

这篇关于算法分析与设计作业3的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！