Leetcode 35: Search Insert Position

 

1. Problem Statement (Simple Explanation):

You are given:

• A sorted array nums of distinct integers (ascending).

• An integer target.

You must:

• Return the index of target in nums if it exists.

• If not, return the index where target should be inserted to keep the array sorted.

You must use an O(log n) algorithm → binary search.

2. Examples:

Example 1:

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

5 exists at index 2.

Output: 2

Example 2:

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

Sorted insertion position:

• 1 (index 0) < 2

• 3 (index 1) > 2 → 2 should go at index 1.

Output: 1

Example 3:

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

7 is greater than all elements, so it would be inserted at index 4 (end of array).

Output: 4

3. Approach – Binary Search for Lower Bound (O(log n)):

We want the smallest index i such that:

• nums[i] >= target

If nums[i] == target, that’s the index.
If nums[i] > target, that’s where target should be inserted.
If no such index exists, insertion position is n (length of array).

This is exactly lower bound.

Algorithm (Step-by-Step):

1. Initialize:

                  left = 0

                  right = n - 1

                  ans = n   // default insertion at end

2. While left <= right:

• mid = left + (right - left) / 2.

• If nums[mid] >= target:

• ans = mid (current candidate position).

• Move left: right = mid - 1 to find smaller index.

• Else (nums[mid] < target):

• Move right: left = mid + 1.

3. Return ans.

Because values are distinct and sorted, this works for both “find exact” and “insertion position”.

Pseudo-code:

Complexity:

Let n = len(nums):

• Time: O(logn)

• Space: O(1)

4. Java code:

5.  C code:

6. C++ code:

7. Python code:

8. JavaScript code: