Problem

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array.

You must write an algorithm with O(log n) runtime complexity.

Examples

Example 1:

Input:
nums = [1,3,5,6], target = 5
Output:
 2

Example 2:

Input:
nums = [1,3,5,6], target = 2
Output:
 1

Example 3:

Input:
nums = [1,3,5,6], target = 7
Output:
 4

Example 4:

Input:
nums = [1,3,5,6], target = 0
Output:
 0

Constraints

  • nums contains distinct values sorted in ascending order.

Solution

Method 1 - Brute force

We can run linear search, which will take O(n) to find the right position to find the insert position.

Method 2 - Recursive Binary Search

Invariant

Suppose left pointer l = 0, and right pointer r = nums.length - 1, then the desired insert position is between [l, r + 1], aka, at minimum it can be at 0th position, as shown example 4, and at max it can be just out of array on right side, as shown in example 3.

Code

Java
class Solution {

	public int searchInsert(int[] nums, int target) {
		return searchInsert(nums, target, 0, A.length - 1);
	}

	private int searchInsert(int[] nums, int target, int start, int end) {
		if (start > end) {
			return start;
		}

		int mid = start + (end - start) / 2;

		if (target < nums[mid]) {
			return searchInsert(nums, target, start, mid - 1);
		} else if (target > nums[mid]) {
			return searchInsert(nums, target, mid + 1, end);
		} else {
			return mid;
		}
	}
}

Complexity

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

Method 3 - Iterative Binary Search

We can run recursive algorithm similar to recursive, solution and in the end return l.

Why we return l and not m or r?

The reason is:

  1. After the loop ends, we know that l > r, aka l >= r + 1
  2. We know from the #Invariant, that insert position is between [l, r + 1], following from (1), this implies l == r + 1
  3. Following from (2), the index is between [l, r+1] = [l, l], which means that l is the desired index. Therefore, we return l as the answer. We can also return r+1 as the result, since l == r+1.

Code

Java
public int searchInsert(int[] nums, int target) {
	int l = 0; // left
	int r = nums.length - 1; // right

	while (l <= r) {
		int m = l + (r - l) / 2; //mid
		if (target == nums[m]) {
			return m;
		}
		if (target > nums[m]) {
			l = m + 1;
		} else if (target<nums[m]) {
			r = m - 1;
		} else {
			return m;
		}
	}

	return l;
}

Complexity

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