‹ DS&A interview · Socratic
DSA · Binary Search · #160

Search Insert Position

Module 59 · difficulty 2/5·⏱ 30:00starts on first keystroke

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. Implement `searchInsert(nums, target)`. You must run in `O(log n)` time.

Examples
  • nums = [1,3,5,6], target = 5 → 2 — 5 is found at index 2.
  • nums = [1,3,5,6], target = 2 → 1 — 2 would be inserted between 1 and 3.
  • nums = [1,3,5,6], target = 7 → 4 — 7 is larger than all elements, inserted at the end.
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
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.