Search Insert Position

L5 Medium Binary Search

Concept

The same binary search that finds a value can find the spot where it would be inserted: when you miss, your final "low" pointer is the correct insertion index.

Given a sorted array of distinct integers nums and a target, return the index where target would be, keeping the order sorted if it were inserted. If target is already present, return its index.

Examples

▸ nums = [1, 3, 5, 6], target = 5

→ 2

▸ nums = [1, 3, 5, 6], target = 2

→ 1

▸ nums = [1, 3, 5, 6], target = 7

→ 4

Progressive Hints

Hint 1 · Nudge

You're looking for the first spot where the array meets or passes the target.

Hint 2 · Plan

Binary search for the first index where nums[i] >= target. That index is the answer, whether the target exists or you're finding where it would slot in.

Hint 3 · Approach

lo = 0, hi = last index. While lo <= hi: mid = the middle; if nums[mid] == target return mid; if nums[mid] < target, lo = mid + 1; else hi = mid - 1. Return lo.

Output

// Run your code to see the output here.