Coding Interview Questions
Problem: Integers in an array are unique and increasingly sorted. Please write a function/method to find an integer from the array who equals to its index. For example, in the array {-3, -1, 1, 3, 5}, the number 3 equals its index 3.
Problem: Integers in an array are unique and increasingly sorted. Please write a function/method to find an integer from the array who equals to its index. For example, in the array {-3, -1, 1, 3, 5}, the number 3 equals its index 3.
What would happen when the value m is greater than the index i? For any k (k>0), the value of element with index i+k should be greater than or equal to m+k, because integers are unique and increasingly sorted in the array. Additionally because m>k, m+k>i+k. Therefore, every element on the right side of index i should be greater than its index in such a case.
Similarly, when the value of element with index i is less than i, every integer on the left side should be less than its index. Please prove it if you are interested.
Therefore, we could reduce the search scope to half for the next step, and it is a typical process for binary search. The solution can be implemented with the following Java code:
public static int getNumberSameAsIndex(int[] numbers) {
if(numbers == null || numbers.length == 0) {
return -1;
}
int left = 0;
int right = numbers.length - 1;
while(left <= right) {
int middle = left + ((right - left) >>> 1);
if(numbers[middle] == middle) {
return middle;
}
if(numbers[middle] > middle) {
right = middle - 1;
}
else {
left = middle + 1;
}
}
return -1;
}
Read full article from Coding Interview Questions