5. 线性查找

有些查找问题要用时间复杂度为O(n)的算法来解决。例如写一个indexof函数,从任意输入字符串中找出某个字母的位置并返回这个位置,如果找不到就返回-1:

例 11.3. 线性查找

#include <stdio.h>

char a[]="hello world";

int indexof(char letter)
{
	int i = 0;
	while (a[i] != '\0') {
		if (a[i] == letter)
			return i;
		i++;
	}
	return -1;
}

int main(void)
{
	printf("%d %d\n", indexof('o'), indexof('z'));
	return 0;
}

这个实现是最直观和最容易想到的,但它是不是最快的算法呢?我们知道插入排序也比归并排序更容易想到,但通常不如归并排序快。那么现在这个问题--给定一个随机排列的序列,找出其中某个元素的位置--有没有比O(n)更快的算法?比如O(lgn)?请读者思考一下。

习题

1、实现一个算法,在一组随机排列的数中找出最小的一个。你能想到的最直观的算法一定是Θ(n)的,想想有没有比Θ(n)更快的算法?

2、在一组随机排列的数中找出第二小的,这个问题比上一个稍复杂,你能不能想出Θ(n)的算法?

3、进一步泛化,在一组随机排列的数中找出第k小的,这个元素称为k-th Order Statistic。能想到的最直观的算法肯定是先把这些数排序然后取第k个,时间复杂度和排序算法相同,可以是Θ(nlgn)。这个问题虽然比前两个问题复杂,但它也有平均情况下时间复杂度是Θ(n)的算法,将上一节习题1的快速排序算法稍加修改就可以解决这个问题:

/* 从start到end之间找出第k小的元素 */
int order_statistic(int start, int end, int k)
{
	用partition函数把序列分成两半,中间的pivot元素是序列中的第i个;
	if (k == i)
		返回找到的元素;
	else if (k > i)
		从后半部分找出第k-i小的元素并返回;
	else
		从前半部分找出第k小的元素并返回;
}

请编程实现这个算法。