You are given a sorted array of integers. The numbers in the array are pairwise

Question

You are given a sorted array of integers. The numbers in the array are pairwise distinct, namely no value appears more than once. Your goal is to find if there is an index 1 k n so that A[k] = k. (Assume that the first index is 1).

(In all algorithm, always explain how and why they work. ALWAYS, analyze the running time complexity of your algorithms. In all algorithms, always try to get the fastest possible. A correct algorithm with slow running time may not get full credit. Always give arguments as for why what you did is correct. You can not just answer ”yes” or ”no”. NEVER write a program. Only write algorithm in the pseudocode)

Explanation / Answer

This algorithm takes O(nlogn) running time.

Algorithm:
1) Intializing the variable count = 0
2) Sorting numbers...( already we done initially)
3) Then removing duplicates from above sorted array
4) for each element array[i]
a) Binary Search for array[i] + k in subarray from i+1 to n-1
b) If array[i] + k found, then increment the count
5) Finally return count

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.