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 n1. That is. you are given an array A[1,....n] such that the prefix A[1,..., k] is sorted in increasing order, the suffix A[k+1,...,n] is sorted in increasing order, and A[n] < A[1].
For example, you might be given the following 16-element array (where k = 10):
9 13 16 18 19 23 28 31 37 42 4 0 2 5 78
Describe and analyze an algorithm to determine if the given array contains a given number 2.