有些查找問題要用時間複雜度為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小的元素並返回;
}請編程實現這個算法。