## Friday, October 10, 2014

### No. 57 - Integer Identical to Index

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.
Analysis: If we scan all integers in the array from beginning to end, we may check whether every element equals its index. Obviously, this solution costs O(n) time.
Since numbers are sorted in the array, let's try to utilize the binary search algorithm to optimize. Supposing we reach the ith element in the array at some step. If the value of element is also i, it is a target integer and let's return it.
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>i, 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;
}

The source code with unit test cases is shared at http://ideone.com/ZSd9kG.
More coding interview questions are discussed in my book< Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this article in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact the author via zhedahht@gmail.com . Thanks.

1. May "because m>k, m+k>i+k" should be "because m>i, m+k>i+k" ?

1. Thanks for your findings. It's a typo, and been fixed.

http://ccppcoding.blogspot.com/
http://appsdevelopment-for-mobiles.blogspot.com/

3. It looks like there are better solutions available in the book
Cracking Programming Interviews: 500 Questions With Solutions by Sergei Nakariakov
http://www.amazon.com/Cracking-Programming-Interviews-Questions-Solutions/dp/1495459802/

4. what if the list contains more than 1 element whose value equals index? e.g.
[-2, 1, 2, 3]

1. The function which returns anyone of 1, 2, or 3 should be Ok.

5. Such a nice article has been posted it is very useful for computer background students.......
Stock future tips

6. Keep up the good work!

Sarkari Result

7. Thanks for the bunch of good resourceful site.I really appreciate your blog,
you have done the great job.
Health beauty blogs

8. hey your blog design is very nice,
clean and fresh and with updated content, make people feel peace and I always like browsing your site.
patiala jokes

9. You are providing outstanding news, very helpful to people plz keep it up ….we are advisory forum provides free trial ,technical news and advise health for trader.