DSA problem
Search Insert Position
Given a sorted array of distinct integers nums and a target value target, return the index where target is found. If it is not present, return the index where it would be inserted to keep the array sorted. You must write an algorithm with O(log n) runtime complexity.
This is the canonical lower_bound problem — find the smallest index i such that nums[i] >= target. If the array contains target, that smallest index is where the element actually lives. If it does not, the same index is the unique position where inserting target keeps the array sorted. Treat the two cases uniformly and the logic stays clean.
Use inclusive bounds with a twist: let lo = 0 and hi = n (not n - 1). The loop while lo < hi shrinks the window using only the mid + 1 increment when nums[mid] < target, and hi = mid when nums[mid] >= target. The invariant is that the answer always lies inside [lo, hi]. When lo catches up to hi, that common value is the insertion index, which sits in [0, n] — note the inclusive right end accounts for the case where target is larger than every element.
The result is O(log n) time and O(1) space. The same template generalizes effortlessly to the rightmost-position (upper_bound) variant, used everywhere from frequency counts to range queries.
Examples
nums = [1,3,5,6], target = 52nums = [1,3,5,6], target = 21nums = [1,3,5,6], target = 74Constraints
- 1 <= nums.length <= 10^4
- -10^4 <= nums[i] <= 10^4
- nums contains distinct values sorted in ascending order.
- -10^4 <= target <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.