Prove that the recursive binary search algorithm shown in Figure 5.30 is correct. That is, prove that the following condition is true, by strong induction on n: For any sorted array A[1 . . . n],...

Prove that the recursive binary search algorithm shown in Figure 5.30 is correct. That is, prove that the following condition is true, by strong induction on n: For any sorted array A[1 . . . n], binarySearch(A, x) returns true if and only if x ∈ A.