Search in a sorted array by value vs. index
  • Posted: 5 years ago
  • Updated: 4 years ago
  • Edit
  • answers (1)
  • views (2486)

You are given a sorted array, say X [ ] where each element is unique. How best can you find an index say i such that element at that index is also i , i.e , X[i] = i .


Posted Answers

We can find the index i with X[i] = i by modifying binary search. The algorithm works as :


  • Compare the middle element of the array and its index.
  • If the middle element of the array is equal to its index, return the index.
  • If the middle element of the array is less than its index, search in the right subarray.
  • If the middle element of the array is greater than its index, search in the left subarray.

Time complexity = \( O(logn) \), space complexity = \( O(1) \).

public int findIndexEqualsValue (int[] array){

low = 0;
high = array.length - 1;

while(low < = high){
/* Find middle index */
middle = (low + high) / 2;

/* Compare middle element and the index */

/* If equals */
if(X[middle] == middle)
return middle;

/* Search in the right half */
elseif(X[middle] < middle)
low = middle + 1;

/* Search in the left half */
else
high = middle - 1;
}
/* no such index exists */
return -1;

}

You need to Sign In to post your solution.