In the analysis of binary search, we assumed that n is a power of 2. This means that n is even (unless it is 1), so there is no middle element. Which element does binarySearch() examine first? The...

In the analysis of binary search, we assumed that n is a power of 2. This means that n is even (unless it is 1), so there is no middle element. Which element does binarySearch() examine first?

The analysis of binary search given in this section is for a worst-case successful search, where we find the target just before we run out of places to look. What is the order of the running time for an unsuccessful search?