Search Insert Position

Solving tips

Reframe 'index of target or where it would go' as one question: the first index where nums[i] >= target (lower bound), which unifies the found and not-found cases.
Use the half-open template: lo=0, hi=len(nums) (exclusive), while lo < hi: if nums[mid] < target then lo=mid+1 else hi=mid; return lo.
Target O(log n) time, O(1) space; bisect.bisect_left gives the same answer if you want the one-liner.
Pitfall: initializing hi = len(nums)-1 with this convention makes the 'insert at the end' answer (len(nums)) unreachable; keep hi exclusive.

Problem

Given a sorted array of distinct integers nums and a target value target, return the index of target if it is present. If it is not present, return the index where it would be inserted to keep the array sorted.

Your algorithm must run in O(log n) time.

Examples

Input: nums = [1, 3, 5, 6], target = 5 → Output: 2 (5 is already at index 2.)
Input: nums = [1, 3, 5, 6], target = 2 → Output: 1 (2 would slot in between 1 and 3, taking index 1.)
Input: nums = [1, 3, 5, 6], target = 7 → Output: 4 (7 is bigger than everything, so it goes at the end.)

Constraints

1 <= nums.length <= 10^4
-10^4 <= nums[i], target <= 10^4
nums contains distinct values sorted in ascending order.
Required time complexity: O(log n).

Think about it first

Hint 1

Whether or not the target is present, the answer is the same well-defined position. Can you phrase both cases ("found at i" and "insert at i") as one question about the array?

Hint 2

The answer is the index of the first element that is greater than or equal to the target (or the array length if none is). That's the classic "lower bound" query — and the array of answers to "is nums at index i >= target?" looks like F, F, …, F, T, T, …, T.

Hint 3

Binary search for that first True. Keep `lo = 0`, `hi = len(nums)` (exclusive), and while `lo < hi`: if `nums[mid] < target`, the boundary is right of mid, so `lo = mid + 1`; otherwise `hi = mid`. When they meet, `lo` is the answer — no special found/not-found cases needed.

TL;DR

Lower-bound binary search (first index with nums[i] >= target) — O(log n) time, O(1) space.

Approach 1 — Brute force (linear scan)

Walk the array left to right and stop at the first element that is >= target; that index is the answer whether the target is present (equal) or absent (greater). If you never stop, the target belongs at the end.

class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        for i, x in enumerate(nums):
            if x >= target:
                return i
        return len(nums)

Time O(n), space O(1). Passes at n <= 10^4, but the problem mandates O(log n) and the scan ignores the sortedness entirely.

Approach 2 — Lower-bound binary search

The insight: “index of target, or where it would be inserted” is one question in disguise: the first index whose element is >= target (length of the array if none). The predicate nums[i] >= target is False for a prefix and True for the rest — a monotone boundary — so binary search can find the first True. This boundary-finding variant is the classical lower bound binary search: it locates the leftmost position where a value could be inserted while keeping order.

class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        lo, hi = 0, len(nums)          # hi is exclusive; answer may be len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] < target:
                lo = mid + 1           # boundary is strictly right of mid
            else:
                hi = mid               # mid could be the boundary
        return lo

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

lo=0, hi=4 → mid=2, nums[2]=5 >= 2 → hi=2.
lo=0, hi=2 → mid=1, nums[1]=3 >= 2 → hi=1.
lo=0, hi=1 → mid=0, nums[0]=1 < 2 → lo=1.
lo == hi == 1 → return 1. ✓

Note there was no “found” check anywhere — target 5 and target 2 flow through the identical code. Time O(log n), space O(1).

Approach 3 — The standard library (`bisect_left`)

The insight: lower bound is so fundamental that Python ships it: bisect.bisect_left(nums, target) returns exactly the leftmost insertion point that keeps nums sorted — the same value Approach 2 computes. bisect is the standard-library implementation of binary-search insertion points on sorted sequences.

import bisect


class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        return bisect.bisect_left(nums, target)

Walkthrough on nums = [1, 3, 5, 6], target = 7: every element is < 7, so the leftmost valid insertion point is 4, the array length. ✓

Time O(log n), space O(1). In an interview, write Approach 2 to show you can, then mention this one to show you know the ecosystem.

Common pitfalls

Initializing hi = len(nums) - 1 with the lo < hi convention — the “insert at the very end” answer (len(nums)) becomes unreachable, failing targets larger than every element.
Handling “found” and “not found” as separate code paths. The lower-bound formulation makes them the same; special-casing invites off-by-ones.
Using the bisect_right boundary (first index with nums[i] > target) — with distinct values it differs from bisect_left exactly when the target is present, returning one past the match instead of the match.
Mixing conventions: hi = mid belongs with exclusive hi and while lo < hi; hi = mid - 1 belongs with inclusive hi and while lo <= hi. Blending them loops or skips.

Pattern takeaway

When a binary-search problem asks for a position rather than a match, reframe it as boundary-finding: define a monotone predicate (here nums at i >= target), then find the first index where it turns True. The half-open [lo, hi) lower-bound template handles found, not-found, and end-of-array cases with zero special-casing — it’s the single most reusable binary-search variant.