Insertion Index Finder

You're in an Apple phone screen and the interviewer says, "Here's a sorted array of integers: [1, 3, 5, 6]. Given a target value, return the index if it's in the array, or the index where it should be inserted. And I need it in O(log n)." That O(log n) constraint is the signal. This is a binary search problem, and it shows up constantly at Google, Adobe, Amazon, Uber, and Yahoo. On Firecode we call it "Insertion Index Finder," but you'll find it across interview platforms under the name Search Insert Position. It is one of the cleanest binary search problems you'll encounter, and a perfect entry point for building fluency with the pattern.

TL;DR

Use standard binary search with left and right pointers. If you find the target, return its index. If the loop ends without finding it, return left, which will be pointing at the correct insertion position. This works because left always advances past elements smaller than the target, so when the search space is exhausted, left sits at the first index where the array value is greater than or equal to the target. O(log n) time, O(1) space.

Why This Problem Matters

Search Insert Position is the foundation for every binary search variant you'll encounter in interviews. Problems like finding the first or last occurrence of a value, searching in rotated arrays, and locating peak elements all build on the same pointer mechanics you'll use here. If you can solve this problem cleanly, including the insertion logic, you have the binary search template memorized. Interviewers at Apple and Google like it as a warm-up because it separates candidates who have internalized binary search from those who try to reconstruct it from scratch each time.

Understanding the Problem

Given a sorted array of unique integers and a target value:

• If the target exists in the array, return its index.
• If the target does not exist, return the index where it should be inserted to maintain sorted order.

Here is the example array:

A few scenarios:

• searchInsert([1, 3, 5, 6], 5) returns 2, since 5 is at index 2.
• searchInsert([1, 3, 5, 6], 2) returns 1, since 2 should be inserted at index 1 (between 1 and 3).
• searchInsert([1, 3, 5, 6], 7) returns 4, since 7 should be inserted at the end.
• searchInsert([1, 3, 5, 6], 0) returns 0, since 0 should be inserted at the beginning.

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

Edge Cases to Consider

1. Target smaller than all elements - insert at index 0
2. Target larger than all elements - insert at the end
3. Target matches the first element - return 0
4. Target matches the last element - return last index
5. Single-element array - either return 0 or 1

Solution Approach

The O(log n) constraint tells you immediately that a linear scan won't cut it. You need binary search. The good news is that this problem uses the standard binary search template almost exactly as you'd write it for a simple "does this value exist?" question. The only twist is what you return when the value is not found.

The Binary Search Template

Binary search on a sorted array works by maintaining two pointers, left and right, that define the current search window. At each step:

1. Compute the middle index: mid = left + (right - left) / 2
2. Compare nums[mid] with the target.
3. If nums[mid] == target, you found it. Return mid.
4. If nums[mid] < target, the target must be to the right. Set left = mid + 1.
5. If nums[mid] > target, the target must be to the left. Set right = mid - 1.
6. If the loop ends without finding the target, left is the insertion index.

Why does step 6 work? Throughout the search, left gets pushed rightward past elements that are too small, and right gets pushed leftward past elements that are too large. When left crosses right, it has landed on the first position where all preceding elements are smaller than the target. That is exactly where the target belongs.

Walkthrough: Target Found

For nums = [1, 3, 5, 6] and target = 5:

The search finds 5 at index 2 after just two iterations. The midpoint calculation initially lands on index 1 (value 3), which is less than 5, so left moves to 2. On the next iteration, mid = 2 and nums[2] = 5 matches the target.

Walkthrough: Target Not Found (Insert in Middle)

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

The target 2 is not in the array. After the loop, left = 1, which is exactly where 2 should go to maintain sorted order (between 1 and 3).

Walkthrough: Insert at End

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

Every element is smaller than 7, so left keeps advancing rightward. When the loop ends, left = 4, which is one past the last index, the correct position to append 7.

Walkthrough: Insert at Beginning

For nums = [1, 3, 5, 6] and target = 0:

Every element is larger than 0, so right keeps retreating leftward. When the loop ends, left is still at 0, the correct position to prepend 0.

Implementation

Prefer a different language? Jump to solutions in other languages.

Here is the Java solution:

public class Solution {
  public int searchInsert(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left <= right) {
      int mid = left + (right - left) / 2;

      if (nums[mid] == target) {
        return mid;
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return left;
  }
}

The entire algorithm fits in about 15 lines. There are no special-case branches for "target is smaller than everything" or "target is larger than everything." The loop invariant naturally handles all of these through the pointer updates.

Midpoint Overflow

In Java, C++, Go, and other languages with fixed-width integers, writing mid = (left + right) / 2 can overflow when left + right exceeds the integer maximum. The safe form is mid = left + (right - left) / 2. In Python this is not a concern because Python integers have arbitrary precision, but it is good practice to use the safe form everywhere so the pattern becomes automatic.

Larger Example

For nums = [-10, -5, 0, 5, 10] and target = 3:

The search narrows to the gap between 0 (index 2) and 5 (index 3). left ends up at index 3, which is where 3 should be inserted.

Complexity Analysis

Time Complexity: O(log n)

Each iteration of the while loop cuts the search space in half. Starting with n elements, the number of iterations is at most log2(n). For an array of 10,000 elements, that is roughly 14 comparisons instead of up to 10,000 with a linear scan.

Space Complexity: O(1)

The algorithm uses three integer variables (left, right, mid) and nothing else. No recursion, no extra arrays, no hash maps.

Common Pitfalls

1. Wrong midpoint formula - Using (left + right) / 2 instead of left + (right - left) / 2 risks integer overflow in Java, C++, and Go. Build the safe version into your muscle memory.

2. Off-by-one in the loop condition - The condition must be left <= right (not left < right). If you use left < right, you skip the case where the search window has exactly one element, which can cause the target to be missed.

3. Returning the wrong value - When the target is not found, you must return left, not right and not mid. right will be one position to the left of where the target belongs, and mid was set during the last iteration, which may not be the insertion point.

4. Forgetting that left can equal nums.length - When the target is larger than every element, left will be pushed past the last valid index. This is correct behavior for insertion, but if your code assumes left is always a valid index, you could introduce a bug in downstream logic.

Interview Tips

When this problem comes up in an interview:

1. Recognize the O(log n) hint. Any time an interviewer mentions logarithmic time on a sorted array, binary search is almost certainly the expected approach.

2. Write the standard binary search template first. Get the loop, the midpoint calculation, and the three-way comparison on the board. Then handle the return value.

3. Explain why left is the insertion index. Interviewers appreciate when you articulate the loop invariant rather than just asserting the answer.

4. Test with boundary inputs. Walk through at least one case where the target goes at the beginning and one where it goes at the end.

5. Mention the connection to lower_bound. In C++, std::lower_bound does exactly this operation. In Python, bisect.bisect_left is the equivalent. Showing awareness of standard library functions demonstrates practical knowledge.

Key Takeaways

• Standard binary search with left <= right naturally produces the correct insertion index when the target is not found. No special-case branches needed.
• The safe midpoint formula left + (right - left) / 2 prevents integer overflow and should be your default in every language except Python.
• O(log n) time and O(1) space make this optimal for sorted array lookups and insertion point queries.
• This problem maps directly to C++ lower_bound and Python bisect_left. Understanding the manual implementation deepens your grasp of what these library functions do under the hood.
• Boundary cases (insert at beginning, insert at end, single-element array) all resolve correctly through the loop mechanics. Trace through at least one boundary case during your interview to build confidence and catch off-by-one errors.

Solutions in Other Languages

Python

class Solution:
    def search_insert(self, nums, target):
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return left

Python's integer division uses //. Since Python integers have arbitrary precision, overflow is not a concern, but the left + (right - left) // 2 form is fine for consistency.

JavaScript

class Solution {
  searchInsert(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      if (nums[mid] === target) {
        return mid;
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return left;
  }
}

JavaScript numbers are 64-bit floats, so integer overflow is not a concern for arrays of this size. Math.floor is needed because JavaScript division produces floating-point results.

C++

#include <vector>

class Solution {
public:
    int searchInsert(std::vector<int> &nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }
};

In C++, std::lower_bound(nums.begin(), nums.end(), target) does the same thing. The manual implementation here is what interviewers expect you to write.

Go

func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums)-1

    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return left
}

Go's sort.SearchInts provides equivalent functionality, but the manual binary search is straightforward and expected in interviews.

TypeScript

function searchInsert(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return left;
}

Kotlin

class Solution {
  fun searchInsert(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1

    while (left <= right) {
      val mid = left + (right - left) / 2
      if (nums[mid] == target) {
        return mid
      } else if (nums[mid] < target) {
        left = mid + 1
      } else {
        right = mid - 1
      }
    }

    return left
  }
}

Swift

class Solution {
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        var left = 0
        var right = nums.count - 1

        while left <= right {
            let mid = left + (right - left) / 2
            if nums[mid] == target {
                return mid
            } else if nums[mid] < target {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }

        return left
    }
}

Scala

class Solution {
  def searchInsert(nums: Array[Int], target: Int): Int = {
    var left = 0
    var right = nums.length - 1

    while (left <= right) {
      val mid = left + (right - left) / 2
      if (nums(mid) == target) {
        return mid
      } else if (nums(mid) < target) {
        left = mid + 1
      } else {
        right = mid - 1
      }
    }
    left
  }
}

Rust

impl Solution {
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        let mut left = 0i32;
        let mut right = nums.len() as i32 - 1;

        while left <= right {
            let mid = left + (right - left) / 2;
            if nums[mid as usize] == target {
                return mid;
            } else if nums[mid as usize] < target {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        left
    }
}

Rust requires explicit i32 types and usize casts for array indexing. right must be i32 (not usize) because it can go negative when the target is smaller than all elements.

Ruby

class Solution
  def search_insert(nums, target)
    left = 0
    right = nums.length - 1

    while left <= right
      mid = left + (right - left) / 2
      if nums[mid] == target
        return mid
      elsif nums[mid] < target
        left = mid + 1
      else
        right = mid - 1
      end
    end

    left
  end
end

Dart

class Solution {
  int searchInsert(List<int> nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left <= right) {
      int mid = left + (right - left) ~/ 2;
      if (nums[mid] == target) {
        return mid;
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return left;
  }
}

Dart uses ~/ for integer division.

C#

public class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.Length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }
}

PHP

class Solution {
    public function searchInsert(array $nums, int $target): int {
        $left = 0;
        $right = count($nums) - 1;

        while ($left <= $right) {
            $mid = $left + intdiv($right - $left, 2);
            if ($nums[$mid] === $target) {
                return $mid;
            } elseif ($nums[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }

        return $left;
    }
}

PHP uses intdiv() for integer division and === for strict equality.

Related Problems

Once you have this binary search template down, try these problems that build on the same pattern:

• Search in a Rotated Sorted Array - Same binary search mechanics, but the array has been rotated at a pivot point.
• Find Minimum in a Rotated Sorted Array - Locate the pivot point itself using binary search.
• Find First and Last Position of Element - Binary search twice: once for the leftmost occurrence, once for the rightmost.
• Peak Element Finder - Binary search on an unsorted array by comparing neighbors.

Remember, consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you're just starting or preparing for your dream job, mastering binary search fundamentals like this will give you a strong foundation for 2026 interviews.

Happy coding!