Sorted array A[1...n] and finding out if A[i] = i:

Question: Given a sorted array of distinct integers A[1...n], you want to find out whether there is an index i for which A[i] = i. Give an algorithm that runs in time O(log n).


Answer: Very easy. Just implement a similar algorithm to binary search.


Possible Solution Code (in Python):

 The above code outputs -1 because there is no such i, and 4 since A[4] = 4.

Infinite array A and finding the index of x:

Question: You are given an infinite array A[.] in which the first n cells contain integers in sorted orde and the rest of the cells are filled with INF. You are not given the value n Describe an algorithm that takes an integer x as input and finds a position in the array containing x, if such a position exists, in O(log n) time.


Answer: The idea is this:

1. Find the index of the end of valid elements, which is n, by using idea similar to binary search (keeping variables left and right, doubling the increment)
2. After getting n, just apply binary search on A[1...n]. Done.

Analysis: Find n by exponentiation takes O(log n). Binary search is O(log n). So, total time is O(log n).


Possible Solution Code (in Python):

The above code should output -1 and 8, as 13122313 is not there!

Removing duplicates in an array of n elements:

Question: You are given an array of n elements, and you notice that some of the elements are duplicates; that is, they appear more than once in an array. Show how to remove all the duplicates from the array in time O(n log n).


Answer:
If you remember the algorithm for mergesort, you should be able to solve this problem. While merging the subarrays and comparing elements, add an extra condition which is "if the elements are equal, remove one of them." Done!


Possible Solution Code(in Python):

The above code outputs an array [1, 2, 3, 4, 5, 8, 9, 10, 14]. Good Luck!