Binary Search Proof

- [10 points] Another property of a sorted array is that binary search can be used to find values in the array. Before we can use this property as the basis of an algorithm, we should investigate the behavior of binary search on an unsorted array. For simplicity, assume that input arrays will not contain any repeated num- bers. Fixing an input array A of length n, we define binary search as: BINARY-SEARCH(A, x, left, right) if right left == 1 return left else median = [(left + right)/2] if x