6. Search Insert Position
easyAsked at WixSearch Insert Position is binary search's cleanest exam: find the target's index in a sorted array, or the index where it WOULD be inserted — which is exactly the lower-bound variant of the search. Wix candidates report it as a screen warm-up where the half-open [lo, hi) convention is the real test: get the boundaries right and the insert position falls out for free, the same primitive a drag-drop layout engine uses to slot a new component into a sorted position array.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Wix loops.
- LeetCode (2026)— Problem #35 'Search Insert Position' — canonical statement, the distinct-sorted guarantee, and the O(log n) requirement.
- Google Search Console (InterviewChamp) (2026-Q2)— Live search-demand data shows candidates searching this problem paired with Wix interview prep.
Problem
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.
Constraints
1 <= nums.length <= 10^4nums is sorted ascending with distinct values-10^4 <= nums[i], target <= 10^4The insert position can be nums.length itself — when the target exceeds every element.
Examples
Example 1
nums=[1,3,5,6], target=52Explanation: 5 exists at index 2 — the found case and the insert case share one answer, which is why a single lower-bound search handles both.
Example 2
nums=[1,3,5,6], target=21Explanation: 2 is absent; it belongs between 1 (index 0) and 3 (index 1), so the insert position is 1 — the index of the first element >= target.
Approaches
1. Linear scan
Walk the array.
- Time
- O(n)
- Space
- O(1)
for(let i=0;i<nums.length;i++) if(nums[i]>=target) return i; return nums.length;Tradeoff: Correct and tiny, but the problem statement explicitly demands O(log n) — on an easy question, ignoring a stated requirement reads worse than a wrong answer on a hard one. State it as the spec of WHAT you're computing (first index with nums[i] >= target), then implement it logarithmically.
2. Binary search
Standard lo/hi sweep; lo lands on insert position.
- Time
- O(log n)
- Space
- O(1)
function searchInsert(nums,target){
let lo=0,hi=nums.length;
while(lo<hi){
const m=(lo+hi)>>1;
if(nums[m]<target) lo=m+1; else hi=m;
}
return lo;
}Tradeoff: The half-open [lo, hi) form with hi starting at nums.length handles every edge — found, insert-in-middle, insert-at-front, insert-past-end — with zero special cases. That uniformity is the entire reason to prefer it over the inclusive-bounds version with its lo <= hi and three-way branching.
Wix-specific tips
Wix candidates report the grading focuses on boundary discipline rather than the algorithm itself: initialize hi = nums.length (not length - 1) so the past-the-end insert position is reachable, keep the loop condition lo < hi, and be able to say WHY lo is the answer when the loop exits — 'lo is the first index whose value is >= target, which is simultaneously the found index and the insert slot.' A layout-builder analogy lands well if invited: slotting a dragged component into a sorted positions array is this exact lower-bound search.
Common mistakes
- Initializing hi = nums.length - 1 with the half-open loop — the insert-past-end case (target greater than everything) becomes unreachable.
- Three-way branching (found / go-left / go-right) when the lower-bound form needs only one comparison — more branches, more off-by-one surface.
- Returning mid on equality inside the loop — harmless here, but it breaks the invariant the moment duplicates are allowed (LC 34).
- Forgetting that (lo + hi) can overflow in fixed-width languages — write lo + ((hi - lo) >> 1) in Java/C++ and say so.
Follow-up questions
An interviewer at Wix may pivot to one of these next:
- Find First and Last Position of Element in Sorted Array (LC 34) — lower-bound AND upper-bound in one problem; the natural next question.
- Search in Rotated Sorted Array (LC 33) — binary search when the sorted invariant is bent by a rotation.
- How would you insert into the array in O(1) after finding the position? (You can't in a flat array — discuss linked structures or gap buffers.)
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does the same code handle both found and not-found cases?
The lower-bound search returns the first index with nums[i] >= target. If the target exists, that IS its index (values are distinct). If it doesn't, every element before that index is smaller — making it precisely the insertion slot. One invariant, two cases.
Why use half-open [lo, hi) instead of inclusive [lo, hi]?
Because the answer space is 0..nums.length inclusive — n+1 possible slots. The half-open form represents the past-the-end slot naturally as hi = nums.length, while inclusive bounds need a special case for it.
What changes if duplicates are allowed?
Nothing in the code — lower bound already returns the FIRST index with nums[i] >= target, i.e. the leftmost insert position. That stability is why interviewers prefer you learn this form: it generalizes to LC 34 untouched.