35. Search Insert Position

35. Search Insert Position

Summary

Find the index of target if it exists in the given array. If not, return the index where target should be inserted.

Conditions:

• The given array is sorted in ascending order.
• nums contains distinct values.

Rules:

• Your algorithm must run in O(log N) time.

Approach

Binary search.

Function

Initialization:

• left = 0
• right = len(nums)

While left < right: mid = (left + right) // 2 if target == nums[mid]: return mid elif target > nums[mid]: move right: left = mid + 1 else: move left: right = mid

Return left.

Example 1:

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

1. left=0, right=4, mid=2 (5) -> return 2.

Example 2:

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

1. left=0, right=4, mid=2 (5) -> go left.
2. left=0, right=2, mid=1 (3) -> go left.
3. left=0, right=1, mid=0 (1) -> go right.
4. left=1, right=1 -> end.

1 is returned.

Example 3:

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

1. left=0, right=4, mid=2 (5) -> go right.
2. left=3, right=4, mid=3 (6) -> go right.
3. left=4, right=4 -> end.

4 is returned.

Complexity

Time Complexity: O(log N) Space Complexity: O(1)