Problem

Given a sorted array of distinct integers, write a function to find the magic index or fixed point in the array, else return -1.

Definition

Magic index or a Fixed point in an array is an index i in the array A such that A[i] = i.

Examples

Example 1:

1
2

Input: nums = [-6, 0, 2, 40]
Output: 2

Example 2:

1
2

Input: nums = [1, 5, 7, 8]
Output: -1

Solution

Method 1 - Linear Search

Naive approach is to do the linear scan and find the magic index in O(n).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public int findMagicIndex(int[] nums) {
	for (i = 0; i < nums.length; i++) {
		if (nums[i] == i) {
			return i;
		}

	}

	return -1;
}

Method 2 - Binary Search

Algorithm

  1. Check the middle element (mid = (start + end) / 2) and compares it to its index in nums[mid]. If they are equal (nums[mid] == mid), return mid as fixed point.
  2. If the middle element is greater than its index search the fixed point in the right half of array
  3. Conversely, if the middle element is less than its index search the fixed point might be in the left half

Why binary search works

Lets analyze case in point 2 in algorithm when mid > nums[mid].

We know the array nums is sorted and the function f(x) is increasing (meaning f(x) > f(y) for x > y).

When mid > nums[mid] , for eg. mid = 4, nums[mid] = 3… searching in left subarray will be useless, because mid will always be more than nums[mid] as elements are distinct. So, we just go to right subarray.

Similarly, when mid < nums[mid], for eg. mid = 4, nums[2] = 6, searching in right subarray will be useless, as mid will never be able to catch up with the nums[i] values. So, we can only go to left subarray.

Because of choosing just 1 path to find the answer, binary search.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public int findMagicIndex(int[] nums) {
	return helper(nums, start, end);
}

private int helper(int[] nums, int start, int end) {
	if (start <= end) {
		int mid = (start + end) / 2;

		if (mid == nums[mid]) {
			return mid;
		}
		// mid > nums[mid] implies fixed point may be on right
		if (mid > nums[mid]) {
			return search(nums, mid + 1, end);
		} else { 
			return search(nums, start, mid - 1);
		}
	}

	return -1;
}

Complexity

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)