Given a sorted array of distinct values, how do you find an index i such that array[i] = i? Let us call it a magic index.
For example if the given array is [-23, -4, 2, 19, 56]. Element 2 is found at array[2]. So the output is 2.
If there no such element in the array we can return -1.
Very obvious approach is to do a linear search to find such an element. This will take O(n) in the worst case.
Since the array is sorted, we can modify the binary search to solve this problem more efficiently.
Using binary search we first visit the middle element of the array.
If array[mid] = mid, simply return mid.
If mid > array[mid], there is no way to find magic index on the left half. Think of an example
[-10, -3, 0, 2, 4, 8]. Here middle index = 3, array[3] = 2. If we go back from index 3, we can only find elements less than 2 because the array is sorted and it has distinct elements. Hence we can safely skip the left half and proceed to search the right half effectively reducing your search space by half.
In the same way, if mid < array[mid], we can ignore the right half and search only left half of the array.
C++ implementation of the above algorithm is given below.
For example if the given array is [-23, -4, 2, 19, 56]. Element 2 is found at array[2]. So the output is 2.
If there no such element in the array we can return -1.
Very obvious approach is to do a linear search to find such an element. This will take O(n) in the worst case.
Since the array is sorted, we can modify the binary search to solve this problem more efficiently.
Using binary search we first visit the middle element of the array.
If array[mid] = mid, simply return mid.
If mid > array[mid], there is no way to find magic index on the left half. Think of an example
[-10, -3, 0, 2, 4, 8]. Here middle index = 3, array[3] = 2. If we go back from index 3, we can only find elements less than 2 because the array is sorted and it has distinct elements. Hence we can safely skip the left half and proceed to search the right half effectively reducing your search space by half.
In the same way, if mid < array[mid], we can ignore the right half and search only left half of the array.
C++ implementation of the above algorithm is given below.