Skip to main content

6. Search Insert Position

easyAsked at Databricks

Given a sorted array, return the index where a target should be inserted to keep it sorted. Databricks uses this to verify you can write a binary search that returns the LEFT bound, which is the canonical primitive for range partitioning.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Databricks loops.

  • Glassdoor (2025-11)— Databricks query-engine interview; precursor to RangePartitioner discussion.
  • LeetCode Discuss (2026-Q1)— Tagged Databricks for the bsearch-left-bound pattern.

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^4
  • -10^4 <= nums[i] <= 10^4
  • nums contains distinct values sorted in ascending order.

Examples

Example 1

Input
nums = [1,3,5,6], target = 5
Output
2

Example 2

Input
nums = [1,3,5,6], target = 2
Output
1

Example 3

Input
nums = [1,3,5,6], target = 7
Output
4

Approaches

1. Linear scan

Walk until you find target or pass it.

Time
O(n)
Space
O(1)
function searchInsert(nums, target) {
  for (let i = 0; i < nums.length; i++) if (nums[i] >= target) return i;
  return nums.length;
}

Tradeoff: Violates the explicit O(log n) requirement.

2. Binary search left bound

Find the first index whose value is >= target. Use the lo <= hi loop with mid = (lo+hi)>>>1 and shrink based on comparison.

Time
O(log n)
Space
O(1)
function searchInsert(nums, target) {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

Tradeoff: Half-open [lo, hi) variant returns the left bound cleanly. hi = nums.length handles 'insert at end' without a special case.

Databricks-specific tips

Databricks grades the half-open binary-search template because it's the same primitive RangePartitioner uses to decide which partition a key belongs to. Be ready for the follow-up: 'now I have sampled boundaries [b1, b2, b3] — given a key k, which partition does it go to?' That's exactly this function. The bonus signal is using >>> 1 not / 2 to avoid float coercion and articulating why the half-open form is less error-prone.

Common mistakes

  • Using mid = (lo + hi) / 2 in languages with integer overflow — use (lo + (hi - lo)) / 2 or unsigned shift.
  • Returning -1 when not found instead of the insertion index.
  • Off-by-one with the closed-interval [lo, hi] form — the half-open [lo, nums.length) variant is safer.

Follow-up questions

An interviewer at Databricks may pivot to one of these next:

  • Return the right bound (first index > target) — same template, flip the comparator.
  • Allow duplicates and return the leftmost occurrence (LC 34 part 1).
  • Spark RangePartitioner: given sampled boundaries, route a key to its partition.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why half-open intervals?

The 'insert at end' case becomes hi = nums.length naturally, with no off-by-one. The closed-interval form needs a final 'return lo' that you have to reason about.

Why >>> 1 not / 2?

Unsigned shift forces integer arithmetic. In languages with bignum like Python, / 2 floats; in C/Java/JS it's a habit that prevents overflow on huge arrays via (lo+hi).

Practice these live with InterviewChamp.AI

Drill Search Insert Position and other Databricks interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →