Suppose you are given a sorted array of n distinct numbers that has been rotated k steps, for some unknown integer k between 1 and n-1. That is, you are given an array A[1.. n) such that some prefix A[1..k] is sorted in increasing order , the corresponding suffix Aſk +1..n) is sorted in increasing order, and A[n]