Course4all

Search Insert Position

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Binary Search.

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(logN)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

StepLRMidnums[Mid]Decision
103133 > 2 → R = 0
200011 < 2 → L = 1
Exit10--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;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionBinary Search
Next Question →Find First and Last Position of Element in Sorted Array