O(lgn)查找算法问题
问题是这样的：
给定一个随机排列的序列，找出其中某个元素的位置－－有没有比O(n)更快的算法？比如O(lgn)？
（问题来源：http://learn.akae.cn/media/ch11s05.html)
我使用归并排序的分治思想写了一个算法：

C/C++ code

#include <stdio.h>#include <string.h>char a[] = "hello world";int indexof(int start, int end, char letter){    int mid, i;        if (start < end) {        mid = (start + end) / 2;        indexof(start, mid, letter);        indexof(mid+1, end, letter);        for (i = start; i < end; i++)            if (a[i] == letter)                return i;    }    return -1;}int main(void){    printf("%d %d\n", indexof(0, strlen(a), 'o'),         indexof(0, strlen(a), 'z'));    return 0;}

但写完才意识到这个算法好像是O(nlgn)的（我初学算法时间复杂度分析，也可能不对）。
大家有没有什么方法？

[解决办法]
不可能低于O(n), 起码每个元素你都得至少读一次.