5. 线性查找

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

例 11.3. 线性查找

  1. #include <stdio.h>
  2.  
  3. char a[]="hello world";
  4.  
  5. int indexof(char letter)
  6. {
  7.     int i = 0;
  8.     while (a[i] != '\0') {
  9.         if (a[i] == letter)
  10.             return i;
  11.         i++;
  12.     }
  13.     return -1;
  14. }
  15.  
  16. int main(void)
  17. {
  18.     printf("%d %d\n", indexof('o'), indexof('z'));
  19.     return 0;
  20. }

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

习题

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

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

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

  1. /* 从start到end之间找出第k小的元素 */
  2. int order_statistic(int start, int end, int k)
  3. {
  4.     用partition函数把序列分成两半，中间的pivot元素是序列中的第i个;
  5.     if (k == i)
  6.         返回找到的元素;
  7.     else if (k > i)
  8.         从后半部分找出第k-i小的元素并返回;
  9.     else
  10.         从前半部分找出第k小的元素并返回;
  11. }

请编程实现这个算法。