For Binary Search why do we need round down the average? Could we round up instead?

Here’s a step-by-step description of using binary search:

1. Let min = 1 and max = n.
2. Guess the average of max and min rounded down so that it is an integer.
3. If you guessed the number, stop. You found it!
4. If the guess was too low, set min to be one larger than the guess.
5. If the guess was too high, set max to be one smaller than the guess.
6. Go back to step two.

Why do we need round down the average? Could we round up instead?

• Short Answer: Rounding up works too.
• Long Answer: What is important is the number of elements to either side of the guess.

  If the number of elements remaining are odd then we will have (n-1)/2 element above and below our guess. No rounding is required. If the number of elements remaining are even then we will have n/2 elements on one side of the guess and n/2-1 elements on the other side, regardless of whether we round up or down. (the rounding determines whether the smaller chunk will be above or below the guess) After we look at the value of our guess we will be able to eliminate the elements above or below our guess.

  The number of guesses required to find a particular element will be different depending on whether we round up or round down. However, if we performed a series of binary searches to find every element, one by one,and took the grand total of the number of guesses from all of these searches, the grand total would be the same regardless of whether we round up or down. This means that the average number of guesses to find an element is the same, regardless of whether we round up or round down.