ソートのオーダーに関する問題。

[ガラ]

質問させていただくのは2回目になるかと思います。
大学生のガラと申します。情報工学科に在籍しています。
C言語は大学2年生までに習う初級程度は大体理解できていると思いますが、あやふやな点もあります。
提出期限が本日の課題に含まれているものであるため、困っています。

質問は大学の課題のアルゴリズムとデータ構造(ソート等)に関する問題についてです。
計算量を示すオーダーについて理解が乏しく、どのようなことを求められているのかもわかりません。
以下のような問題です。

大きさnの相異なる整数要素からなるソート済みの配列a,a[1] < a[2] < ... <a[n]が与えられている。
入力として与えられている整数lに対し、a = lとなるiが存在すればそのようなiを返し、どのi(1<=i<=n)に対してもa≠lなら0を返すようなO(logn)ステップで動作するアルゴリズムを構成せよ。C言語などに基づく擬似コードでよい。

この問題に対して、以下のようなアルゴリズムでは題意を満たさないように思えるのですが、どうすればよいのでしょうか。

for (i = 1, i <= n, i++) {
if (a == l)
return i;
}
return 0;

ご教授願います。

[ドラ]

二分探索（Binary Search）しろって事だと思います。

>以下のようなアルゴリズムでは題意を満たさないように思えるのですが
はい。線形探索ではO(n)になってしまいます。

[ガラ]

int low = 1;
int high = n;
int i;
while (low <= high) {
i = (low + high) / 2;
if (a == l) {
return i;
}else if (a < l) {
low = i + 1;
}else if (a > l) {
high = mid -1;
}
}
return 0;


二分探索だとこのような感じでしょうか。

[sizuma]

＞提出期限が本日の課題に含まれているものであるため、困っています。
すっごい分かりづらいです。

＞二分探索だとこのような感じでしょうか
擬似コードでいいって書いてますけど、普通にコンパイルできて動作するように作ったほうがいいですよ。