Search Insert Position

LeetCode 35 | Difficulty: Easy

Easy

Problem Description

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

- `1 <= nums.length <= 10^4`

- `-10^4 <= nums[i] <= 10^4`

- `nums` contains **distinct** values sorted in **ascending** order.

- `-10^4 <= target <= 10^4`

Topics: Array, Binary Search

---

Approach

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

---

Solutions

Solution 1: C# (Best: 152 ms)

Metric	Value
Runtime	152 ms
Memory	N/A
Date	2017-10-16

Solution

public class Solution {
    public int SearchInsert(int[] nums, int target) {
     int low = 0, high = nums.Length-1, mid = 0;
    while (low <= high)
    {
        mid =  low + (high - low) / 2;
        if(nums[mid] == target) return mid;
        else if(nums[mid] > target)
        high = mid-1;
        else low = mid+1;
    }
    return low;
    }
}

---

Complexity Analysis

Approach	Time	Space
Binary Search	$O(log n)$	$O(1)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Precisely define what the left and right boundaries represent, and the loop invariant.