Search Algorithm

Given a sorted array of $n$ distinct integers and a target $t$, find the index of $t$ (or report absence) in $\mathcal{O}(\log n)$ time.

Then discuss what you would change if the array were:

A. Unsorted.

B. Sorted but with millions of lookups against the same array.