Let A[0,...,n-1] be a sorted array of distinct integers. That is, the elements of the array...

 

Transcribed Image Text:

Let A[0,...,n-1] be a sorted array of distinct integers. That is, the elements of the array satisfy the relationship - A[0] < A[1] < A[2] < ... < A[n 1]. An index i is said to be a stable point if A[i]=i. For example, of the arrays [-3, 0, 2, 8, 11] and [-14, -7, 29, 41, 68], the first array has a stable point A[2] = 2, while the second array does not have a stable point. Describe an algorithm which, given a sorted array of distinct integers, computes a stable point i or correctly reports that no such point exists. Try to make your algorithm as efficient as possible, and justify its running time. (Hint: modify binary search) Let A[0,...,n-1] be a sorted array of distinct integers. That is, the elements of the array satisfy the relationship - A[0] < A[1] < A[2] < ... < A[n 1]. An index i is said to be a stable point if A[i]=i. For example, of the arrays [-3, 0, 2, 8, 11] and [-14, -7, 29, 41, 68], the first array has a stable point A[2] = 2, while the second array does not have a stable point. Describe an algorithm which, given a sorted array of distinct integers, computes a stable point i or correctly reports that no such point exists. Try to make your algorithm as efficient as possible, and justify its running time. (Hint: modify binary search)