1.问题

写出两种检索算法：在一个排好序的数组T[1…n]中查找x，如果x在T中，输出x在T的下标j；如果x不在T中，输出j=0.

2.解析

1. 顺序查找：这是最简单也是最先想到的算法，但是它的缺陷也很明显，如果要找到的数在数组的末尾，那么要找到这个数就必须遍历一遍数组，当这个数组很大时，找到这个数所要花费的时间是我们无法接受的。
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.源码

顺序查找
二分查找