PPractick

The problem

A leaderboard keeps its scores in a sorted array with no duplicates. When a player finishes a game, the app must either find their score if it's already listed or report the index where it would be inserted to keep the list sorted, so the new entry can be animated into place. That position is exactly the lower bound of the score: the first index whose value is at least the target. One binary search answers both "is it here?" and "where would it go?".

Example: [1, 3, 5, 6], target 2 → 1 (it would go between 1 and 3).

Function signature

int searchInsert(const vector<int>& nums, int target);  // index of target, or where it would be inserted

Test cases

Input (nums, target)	Output	Explanation
([1, 3, 5, 6], 5)	2	Found at index 2
([1, 3, 5, 6], 2)	1	Would go before 3
([1, 3, 5, 6], 7)	4	Larger than everything: append at the end
([1, 3, 5, 6], 0)	0	Smaller than everything
([1], 1)	0
([], 3)	0	Empty array

(Confirm: the array is sorted with distinct values; O(log n) is expected.)

How interviewers phrase it

• "Return the index if the target is found, otherwise the index where it would be inserted" (LeetCode 35).
• A quick check that you know lower bound, often before harder binary search problems.

Clarifying questions to ask

1. Are the values distinct?
2. If the target is found, should I return its index? (Yes.)
3. Is O(log n) required?

Follow-ups to expect

1. "Why is this just lower bound?"
2. "What if the array had duplicates?"
3. "Library equivalent?"
4. "Complexity?"

Related questions

• Search X in sorted array Easy
• Lower Bound Easy
• Upper Bound Easy
• Floor and Ceil in Sorted Array Easy
• Count Occurrences in a Sorted Array Easy
• Kth Missing Positive Number Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in