algorithm: trying to get the index from array where |A[i] - i| <=c in log(N) with a divide and conquer algorithm

Question

Input: a sorted array A (all elements are integer and distinct in increasing order) and c (integer)

Output: return a randomly selected index such that this index meet the requirement: |A[i]-i| <= c

It should run within O(logN) time in the worst case.

My original thought was to binary search index i, such that A[i] = 0 or the closet to 0. Then this index divides the array into 2 parts.

The left part contains element < 0 and the right part contains element > 0.

For the right part, run a binary search-liked algorithm to check the mid-value and see whether A[mid]-mid <=c, if so, go to [mid+1, end]. However, I found this problem when I have the following example:

c=2
i     0  1  2  3  4  5  6  7
A[i] -5 -4  -1 0  1  5  8  9

A[4] does not meet |A[4]-4| <=2 but it will be included in my algorithm. So I have no idea about this question at all now...

Answer 1

Let's take a look at the data. It follows from A containing distinct sorted integers that for any pair of successive elements, A[i] <= A[i + 1] - 1.

The search keys for these elements are A[i] - i and A[i + 1] - i - 1. Subtracting i from both sides of the inequality shows that two successive keys are equal or increasing if positive, and equal or decreasing if negative.

If the problem did not ask for absolute values, it would be trivial to solve. You would just check the first element, and either it would meet there criterion, or no element would.

The absolute value means that your keys can be decreasing, increasing or steady. There decreasing region is always to the left of the minimum and the increasing region is to the right.

You can find the minimum in log(N) time with something similar to a binary search, but from both ends. The trick is to figure out which side of the midpoint to look at for the minimum.

Start with the two ends and the center of the array. Pick a midpoint for each half. If the halfway point is less than the center, the minimum is in that half: adjust the bounds to just that half and proceed. If not, that's your new endpoint for that half. You will do at most 2 * log(N/2) = O(log(N)) operations.

You can terminate early when your bounds all differ by at most 1, or you hit upon an element that satisfies the condition early.

If you truly do need a random element, rather than an arbitrary one, you will need to search for the bounds that satisfy the condition in each half. This will not add to the complexity since O(4 log(N/2)) = O(log(N)). Presumably picking a random number from that interval is O(1).

I leave this last part as an exercise for the reader if necessary.