顺序查找以及折半查找

---

一、顺序查找

顺序查找的基本思路如下：

• 顺序扫描序列表
• 若匹配，返回下标
• 若不匹配，返回-1

//无监视哨的顺序查找
int SeqSearch(Record *r, int n, int k)
{
	int i = 0;
	while (i < n&&r[i].key != k)
		i++;
	if (i < n)
		return i;
	return -1;
}
//有监视哨的顺序查找
int SeqSearch2(Record *r, int n, int k)
{
	int i = 0;
	r[n].key = k;
	while (r[i].key != k)
		i++;
	if (i < n)
		return i;
	return -1;
}

测试结果:

二、折半查找

折半查找的基本思想是在有序表中，取中间元素作为比较对象。

• k==mid ， 成功
• k < mid ， 左半区继续查找
• k>mid ， 右半区继续查找

重复上述查找过程，直到查找成功，或所查找的区域无记录，查找失败。

//折半查找非递归算法
int BiSearch(Record r[], int n, int k)
{
	int low = 0;
	int high = n - 1;
	while (low <= high)
	{
		int mid = (low + high) / 2;
		if (r[mid].key == k)
			return mid;
		else if (r[mid].key < k)
			low = mid + 1;
		else high = mid - 1;
	}
	return -1;
}

//折半查找递归算法
int BiSearch2(Record r[], int low, int high, int k)
{
	if (low>high)
		return -1;
	else
	{
		int mid = (low + high) / 2;
		if (r[mid].key == k)
			return mid;
		else
			if (r[mid].key < k)
				return BiSearch2(r, mid + 1, high, k);
			else
				return BiSearch2(r, low, mid - 1, k);
	}
}

测试结果：