Find Where a Value Belongs in a Sorted Array

Easy10–15 min

Topics

ArrayBinary Search

Companies

AmazonMicrosoftFacebook

Given a sorted array of distinct integers nums and an integer target, return the index of target if it's found — otherwise return the index where it would be inserted to keep the array sorted. Aim for O(log n) time by binary-searching for the leftmost position whose value is greater than or equal to target.

Test Case 1:

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

Output:2

Explanation:5 is already at index 2.

Test Case 2:

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

Output:1

Explanation:2 isn't present, but it would sit between 1 and 3 — index 1.

Test Case 3:

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

Output:4

Explanation:7 is larger than every element, so it belongs right at the end.

Constraints

◆1 ≤ nums.length ≤ 10⁴
◆-10⁴ ≤ nums[i] ≤ 10⁴
◆nums contains distinct values sorted in ascending order
◆-10⁴ ≤ target ≤ 10⁴

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (sorted, comma-separated) — 1-12 integers, sorted ascendingtarget

1	class Solution {
2	public int searchInsert(int[] nums, int target) {
3	int lo = 0, hi = nums.length - 1, ans = nums.length;
4	while (lo <= hi) {
5	int mid = lo + (hi - lo) / 2;
6	if (nums[mid] >= target) {
7	ans = mid;
8	hi = mid - 1;
9	} else {
10	lo = mid + 1;
11	}
12	}
13	return ans;
14	}
15	}
16

↑lo

↑hi

Variables

lo0

hi3

ans4

INITIALIZE

Search [0, 3] for the leftmost index where nums[i] ≥ 5. Default ans to 4 (insert at the end) until something qualifies.

Step 1 / 4

Approach & Solutions

Brute Force — Linear Scan

Brute

Walk left to right and return the first index whose value is already ≥ target — that's exactly where target would be inserted to keep the array sorted. If nothing qualifies, target belongs past the last element. Correct, but it never uses the fact that nums is sorted.

TimeO(n)

SpaceO(1)

Java

Try it out

class Solution {
    public int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) return i;
        }
        return nums.length;
    }
}

Optimal — Binary Search (Lower Bound)

Optimal

Binary-search for the leftmost index whose value is ≥ target. Whenever nums[mid] ≥ target, mid is a valid insertion point, but a smaller index further left might also qualify — record it as the current best answer and keep searching left. Otherwise, target must sit to the right of mid.

TimeO(log n)