n performing a binary search for x in a sorted n-element array A[1 . . . n] (see Figure 6.17(a)), the first thing we do is to compare the value of x and the value of A ⌊ 1+n 2 ⌋ . Assume that all...

n performing a binary search for x in a sorted n-element array A[1 . . . n] (see Figure 6.17(a)), the first thing we do is to compare the value of x and the value of A ⌊ 1+n 2 ⌋ . Assume that all elements of A are distinct. How many elements of A are less than A ⌊ 1+n 2 ⌋ ? How many are greater? Write your answers as simply as possible.

Figure 6.17

Figure 6.17: Binary Search