On average, assuming that each element is equally likely to be searched, binary search makes \lfloor \log_2 (n) \rfloor + 1 - (2^{\lfloor \log_2 (n) \rfloor + 1} - \lfloor \log_2 (n) \rfloor - 2)/n iterations when the target element is in the array. This is approximately equal to \log_2(n) - 1 iterations. When the target element is not in the array, binary search makes \lfloor \log_2 (n) \rfloor + 2 - 2^{\lfloor \log_2 (n) \rfloor + 1}/(n + 1) iterations on average, assuming that the range between and outside elements is equally likely to be searched.
