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 小的元素并返回;
   }

请编程实现这个算法。