Suppose that you are given a sorted sequence of distinct integers {a1, a2, ..., an}. give an o (lgn) algorithm to determine whether there exists an i index such as ai

Since the sequence is sorted, you can use the binary search, which is of O (lg2). You can google binary search, or inspire from the following.

Basically, the algorithm looks like the following:

checkMiddle (ai, a1, n)

if (n==0) return (-1) / / key ai not found

k = (1+n) / 2;

if (a_k = ai) return (k)

else

if (a_k>ai

checkMiddle (ai, a_1, k)

else

checkMiddle (ai, a_ (k+1), n-k)

endif

You may have to tune and check, but the basic idea is there.

Also, concerning computing algorithms, you are better off with posting it under technology and computers.