### Search in a sorted array by value vs. index sortedarray array searching    Posted: 5 years ago Updated: 4 years ago Edit answers (1) views (2950)

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: 5 years ago 0 0 Edit 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; }