Interview question - Search in sorted array X for index i such that X[i] = i
Solution 1
This can be done in O(logN)
time and O(1)
space by using a slightly modified binary search.
Consider a new array Y
such that Y[i] = X[i] - i
Array X : -3 -1 0 3 5 7
index : 0 1 2 3 4 5
Array Y : -3 -2 -2 0 1 2
Since the elements in X
are in increasing order, the elements in the
new array Y
will be in non-decreasing order. So a binary
search for 0
in Y
will give the answer.
But creating Y
will take O(N)
space and O(N)
time. So instead of
creating the new array you just modify the binary search such that a
reference to Y[i]
is replaced by X[i] - i
.
Algorithm:
function (array X)
low = 0
high = (num of elements in X) - 1
while(low <= high)
mid = (low + high) / 2
// change X[mid] to X[mid] - mid
if(X[mid] - mid == 0)
return mid
// change here too
else if(X[mid] - mid < 0)
low = mid + 1;
else
high = mid - 1;
end while
return -1 // no such index exists...return an invalid index.
end function
Solution 2
There are some faster solutions, averaging O(log n) or in some cases O(log log n) instead of O(n). Have a google for "binary search" and "interpolation search", you're likely to find very good explanations.
If the array is unsorted, then yes, the element is anywhere and you can't get under O(n), but that's not the case with sorted arrays.
--
Some explanation on interpolation search as requested:
While the binary search only concerns with comparing two elements in terms of "greater / not greater", the interpolation search tries to also make use of numerical values. The point is: You have a sorted range of values from 0 to, say, 20000. You look for 300 - binary search would start at the half of range, at 10000. The interpolation search guesses that 300 would probably be somewhere closer to 0 than 20000, so it would check the element 6000 first instead of 10000. Then again - if it's too high, recurse into lower subrange, and it's too low - recurse into upper subrange.
For a big array with +- uniform distribution of values, interpolation search should behave much faster than binary search - code it and see for yourself. Also, works best if first you use one interpolation search step, then one binary search step, and so on.
Note that it's the thing a human does intuitively when looking up something in a dictionary.
Solution 3
Its not require to think in terms of any array Y
as suggested in answer by @codaddict.
Use binary search and check the middle element of given array, if it is lower than its index, than we do not need to check for any lower index because the array is
sorted and so if we move to the left, subtracting m indexes and (at least) m value, all subsequent elements will also be too small. E.g. if arr[5] = 4
then arr[4] <= (4 - 1)
and arr[3] <= (4 - 2)
and so on. Similar logic can be apply if middle element is greater than its index.
Here is simple Java
implementation:
int function(int[] arr) {
int low = 0;
int high = arr.length - 1;
while(low <= high) {
int mid = high - (high - low) / 2;
if(arr[mid] == mid) {
return mid;
} else if(arr[mid] < mid) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // There is no such index
}
Note that the above solution would work only if all elements are distinct.
Solution 4
I think this would be faster.
Start in the middle of the list
If X[i] > i then go to the middle of the remaining left side
if X[i] < i then go the middle of the remaining right
Keep doing that and it will reduce the number of possible elements by half for each loop
Solution 5
You can perform a binary search: search the middle, if the value is lower than the index, than no lower index will contain the same value.
Then you search the higher half, and continue till you find the element, or reach one element span.
Admin
Updated on June 13, 2020Comments
-
Admin almost 4 years
I was asked the following question in my interview yesterday:
Consider a Java or C++ array say
X
which is sorted and no two elements in it are same. How best can you find an index sayi
such that element at that index is alsoi
. That isX[i] = i
.As clarification she also gave me an example:
Array X : -3 -1 0 3 5 7 index : 0 1 2 3 4 5 Answer is 3 as X[3] = 3.
The best I could think was a linear search. After the interview I though a lot on this problem but could not find any better solution. My argument is: the element with the required property can be anywhere in the array. So it could also be at the very end of the array so we need to check every element.
I just wanted to confirm from the community here that I'm right. Please tell me I'm right :)
-
Alexey Malistov over 13 years+1 for
interpolation search
reference. It is described in D. Knuth books also. -
codaddict over 13 years"You can perform a binary search" - What is your key?
-
Admin over 13 yearsThank you for the explanation. I knew binary search but never though I'd to apply it in this manner.
-
Admin over 13 yearsCan you please explain how to apply interpolation search for this problem?
-
Mor Shemesh over 13 yearsthe value of the cell is the "value" and the index is the "key".
-
Mor Shemesh over 13 years(under the assumption the length of the array is knows)
-
Steve Jessop over 13 years-1, you haven't explained how to apply interpolation search to this problem. The non-obvious step is that for integers, if
x[i]
is strictly increasing, thenx[i]-i
is non-decreasing. -
Steve Jessop over 13 years-1, the value of the cell is not the value to use in the binary search.
-
Mor Shemesh over 13 yearsyou can still use it as part of numeric comparison to the cells value
-
Kos over 13 yearsI don't know what you're talking about - as I've been taught, the only algorithmic difference between binary search and interpolation search is the method of choosing the "pivot point". I've implemented it exactly as described and it worked as expected with decent results. Also, even if you have something of practical importance to add (which may be true and I'd like to hear that), a downvote isn't appropriate for a technically correct and - I believe - helpful answer.
-
Admin over 13 yearsKos: Thanks for the explanation. But I still don't get how to apply interpolation search for this prlblem :(
-
JOTN over 13 yearsSince they said a Java or C++ array, it's a safe assumption we know how long it is.
-
Steve Jessop over 13 years@Kos: the question is not, "how do I find an index
i
so thatx[i] == 300
". The question is, "how do I find an indexi
so thatx[i] == i
". Without accounting for that, I don't see how this answer can be considered correct (although it's certainly a good description of an interpolation search). -
Kos over 13 years... Steve you're right :), for some reason till now I failed to notice what's this problem is about; aparrently I need to give up on my programming skills and focus on reading skills instead. John, for interpolation search just refer to Codaddict's post and replace the line
int mid = ...
for appropriate one for interpolation search. Sorry for the confusion, everyone :). -
Admin over 13 years@codaddict: Is "non-decreasing order" ascending order?
-
djna over 13 years@Monomer - an array of identical elements could be seen as not ascending, but it's certainly non-decreasing. The algorithm depends on the non-decreasing-ness, but copes with an array of equal values.
-
Srikanth over 13 yearsI don't understand why the resulting array Y is non-decreasing. Lets say X is [3,3,3,3] then Y would be [3, 2, 1, 0]. It is clearly decreasing. I think I'm missing something here. can someone Please enlighten me?
-
codaddict over 13 years@Srikanth: The question has a requirement "no two array elements are same".
-
Tony Delroy over 13 years+1: I don't think you explained it quite as clearly as some others (e.g. JOTN), but seems you were first with the answer.
-
Ricko M over 13 yearsAlso , shouldn't you be able to pick out the '0' entry while building the new array ? That makes it linear.. right ?
-
Serge Dundich about 13 yearsEverything is fine except one thing: you didn't really prove that array Y is non-decreasing (which is true for the conditions given) and thus you didn't highlight the condition that makes it non-decreasing. What changes if you use floating point numbers instead of integers? In your explanation nothing changes but the algorithm is wrong for the floats and true algorithm is o(n).
-
GlenPeterson over 11 years+1 Great answer. It's worth noting that Java has built-in Arrays.binarySearch() and Collections.binarySearch() methods so that you don't have to implement your own (Java 7 at least). Knowing this could save you a lot of time in an interview. It probably won't help in this case, but I wonder if you could define a key object with an equals method like:
equals(Integer that) { return that - X.indexOf(that) == 0; }
or a compareTo method likecompareTo(Integer other) { return other - axList.indexOf(other); }
I just tried and Java didn't want to let me for type-safety reasons. -
Vasu almost 11 yearsIts not necessary to think in terms of a new array
Y
. See my answer link. -
dchhetri almost 11 yearsWhat if
arr[5] = 3
, then solution can be inarr[4]
still or be inarr[6]
. I don't think we can pick a direction in this case with the above code -
Vasu almost 11 years@user814628, in this case
arr[4]
must be less than 3 asarr
is sorted, and so we must look from index6
onwards for solution. -
Boris Dalstein almost 11 years+1 that's my favourite answer for the sweet explanation in terms of a new array Y. But simple reasoning as suggested here also works well and give the same code.
-
Konstantin Milyutin almost 8 yearsit can't be O(n log n), you access each element at most once.