$.$ 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 sux A$[$k $+1..$ n$]$ is sorted in increasing

order, and A$[$n$]<$ A$[1].$

For example, you might be given the following $-$element array $($where

k $=10)$:

$9131618192328313742134578$

$($a$)$ Describe and analyze an algorithm to compute the unknown integer k$.$

$($b$)$ Describe and analyze an algorithm to determine if the given array

contains a given number x