Search Insert Position

Master this topic with zero to advance depth.

Search Insert Position

Given a sorted array of distinct integers nums and a target value target, return the index if the target is found. If not, return the index where it would be if it were inserted in order. Your algorithm must run in $O(\\log N)$ time.

Easy

Examples

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

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

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

Approach 1

Level I: Brute Force (Linear Scan)

Intuition

Since the array is sorted, we can simply find the first element that is greater than or equal to the target. That index is our insertion point.

⏱ $O(N)$💾 $O(1)$

Detailed Dry Run

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

0: 1 < 2
1: 3 >= 2. Return 1.

java

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;
    }
}

Approach 2

Level III: Optimal (Binary Search - Lower Bound)

Intuition

Binary search finds the 'lower bound'—the first index where nums[index] >= target. When the loop while (l <= r) exits, the l pointer naturally lands on the correct insertion index.

⏱ $O(\\log N)$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	nums[Mid]	Decision
1	0	3	1	3	3 > 2 → R = 0
2	0	0	0	1	1 < 2 → L = 1
Exit	1	0	-	-	Return L = 1

java

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }
}

← Previous QuestionBinary Search

Next Question →Find First and Last Position of Element in Sorted Array

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.