However, for this problem, this is not a good technique because we are not taking advantage of the fact that A is sorted. Otherwise, it must be in the right half. Binary search, on the other hand takes a little longer. However, suppose we were looking for 25. So this time binary search is better.
Binary search is a little trickier, though.
We begin the analysis by noting that we are cutting our search space in half each time. We need to notice a tendency. This is solved using the log 2 .