PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

An Uber software engineer onsite coding question asking you to implement binary search on a sorted integer array from scratch, in both iterative and recursive form. It covers plain search, first/last occurrence with duplicates, the insertion-index variant, overflow-safe midpoint computation, loop invariants and correctness, and time/space complexity analysis.

  • Medium
  • Uber
  • Coding & Algorithms
  • Software Engineer

Implement binary search from scratch

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

##### Question Implement binary search on a sorted integer array **without using any library helpers** (no `bisect`, `Arrays.binarySearch`, etc.). Provide **both iterative and recursive** versions, and address each of the following: 1. **Basic search.** Return the index of the target if it is present, or `-1` if it is absent. 2. **First occurrence.** When the array contains duplicates, return the index of the *first* occurrence of the target. 3. **Last occurrence.** When the array contains duplicates, also be able to return the index of the *last* occurrence of the target. 4. **Insertion index.** If the target is absent, return the index at which it could be inserted while keeping the array sorted (the classic "search insert position"). 5. **Integer overflow.** Compute the midpoint in a way that avoids integer overflow on large indices. 6. **Correctness & invariants.** Clearly state your loop invariant and boundary handling (inclusive vs. exclusive bounds), and argue why the search terminates and is correct. 7. **Complexity.** State the time and space complexity of each variant. **Example** ``` nums = [1, 2, 2, 2, 5, 7], target = 2 basic search -> any index in {1, 2, 3} first occ. -> 1 last occ. -> 3 nums = [1, 3, 5, 6], target = 4 basic search -> -1 insertion idx -> 2 ```

Quick Answer: An Uber software engineer onsite coding question asking you to implement binary search on a sorted integer array from scratch, in both iterative and recursive form. It covers plain search, first/last occurrence with duplicates, the insertion-index variant, overflow-safe midpoint computation, loop invariants and correctness, and time/space complexity analysis.

Binary Search — Basic Search

Implement binary search on a sorted integer array WITHOUT using any library helpers (no bisect, Arrays.binarySearch, etc.). Return the index of `target` if it is present in `nums`, or `-1` if it is absent. The array is sorted in non-decreasing order. If the target appears multiple times, returning any valid matching index is acceptable, but these tests use distinct-value arrays for the basic search so the answer is unique. Use an overflow-safe midpoint computation: `mid = lo + (hi - lo) / 2` rather than `(lo + hi) / 2`. Example: nums = [1, 3, 5, 6], target = 5 -> 2 nums = [1, 3, 5, 6], target = 2 -> -1

Constraints

  • 0 <= len(nums) <= 10^5
  • nums is sorted in non-decreasing order
  • -10^9 <= nums[i], target <= 10^9
  • Do not use any built-in search helpers (bisect, Arrays.binarySearch, etc.)

Examples

Input: ([1, 3, 5, 6], 5)

Expected Output: 2

Explanation: 5 sits at index 2.

Input: ([1, 3, 5, 6], 2)

Expected Output: -1

Explanation: 2 is absent; return -1.

Input: ([], 7)

Expected Output: -1

Explanation: Empty array — nothing to find.

Input: ([4], 4)

Expected Output: 0

Explanation: Single-element match at index 0.

Input: ([4], 9)

Expected Output: -1

Explanation: Single-element no match.

Input: ([-5, -3, -1, 0, 2], -3)

Expected Output: 1

Explanation: Works with negatives; -3 is at index 1.

Input: ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 1)

Expected Output: 0

Explanation: First element boundary.

Input: ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 10)

Expected Output: 9

Explanation: Last element boundary.

Hints

  1. Maintain an inclusive search window [lo, hi]. Invariant: if target exists, its index is within [lo, hi].
  2. Compute the midpoint as lo + (hi - lo) // 2 to avoid integer overflow in fixed-width languages.
  3. When nums[mid] < target, the answer (if any) is strictly to the right, so set lo = mid + 1; otherwise move hi = mid - 1. The loop ends when lo > hi (empty window).

Binary Search — First Occurrence (Lower Bound)

Given a sorted integer array `nums` (which may contain duplicates) and a `target`, return the index of the FIRST (leftmost) occurrence of `target`, or `-1` if it is absent. Do not use any library helpers. The trick: on a match, do not return immediately — record the candidate index and keep searching the LEFT half so an earlier duplicate can override it. Example: nums = [1, 2, 2, 2, 5, 7], target = 2 -> 1 nums = [1, 2, 2, 2, 5, 7], target = 4 -> -1

Constraints

  • 0 <= len(nums) <= 10^5
  • nums is sorted in non-decreasing order and may contain duplicates
  • -10^9 <= nums[i], target <= 10^9
  • Do not use any built-in search helpers

Examples

Input: ([1, 2, 2, 2, 5, 7], 2)

Expected Output: 1

Explanation: First of the three 2s is at index 1.

Input: ([1, 2, 2, 2, 5, 7], 5)

Expected Output: 4

Explanation: Unique value 5 at index 4.

Input: ([1, 2, 2, 2, 5, 7], 4)

Expected Output: -1

Explanation: 4 is absent.

Input: ([], 3)

Expected Output: -1

Explanation: Empty array.

Input: ([5, 5, 5, 5], 5)

Expected Output: 0

Explanation: All duplicates — first is index 0.

Input: ([7], 7)

Expected Output: 0

Explanation: Single-element match.

Input: ([-3, -3, -1, 0], -3)

Expected Output: 0

Explanation: Leftmost negative duplicate at index 0.

Input: ([1, 1, 2, 3, 3, 3], 3)

Expected Output: 3

Explanation: First 3 is at index 3.

Hints

  1. A plain binary search returns the first match it lands on, which may be a middle duplicate, not the leftmost one.
  2. On nums[mid] == target, store mid as the best answer so far, then move hi = mid - 1 to keep probing the left half.
  3. The 'equal' and 'greater' branches both move hi left, so you can merge them: if nums[mid] >= target, go left; else go right — recording the index only on exact equality.

Binary Search — Last Occurrence (Upper Bound)

Given a sorted integer array `nums` (which may contain duplicates) and a `target`, return the index of the LAST (rightmost) occurrence of `target`, or `-1` if it is absent. Do not use any library helpers. Mirror image of first-occurrence: on a match, record the candidate index and keep searching the RIGHT half so a later duplicate can override it. Example: nums = [1, 2, 2, 2, 5, 7], target = 2 -> 3 nums = [5, 5, 5, 5], target = 5 -> 3

Constraints

  • 0 <= len(nums) <= 10^5
  • nums is sorted in non-decreasing order and may contain duplicates
  • -10^9 <= nums[i], target <= 10^9
  • Do not use any built-in search helpers

Examples

Input: ([1, 2, 2, 2, 5, 7], 2)

Expected Output: 3

Explanation: Last of the three 2s is at index 3.

Input: ([1, 2, 2, 2, 5, 7], 5)

Expected Output: 4

Explanation: Unique value 5 at index 4.

Input: ([1, 2, 2, 2, 5, 7], 4)

Expected Output: -1

Explanation: 4 is absent.

Input: ([], 3)

Expected Output: -1

Explanation: Empty array.

Input: ([5, 5, 5, 5], 5)

Expected Output: 3

Explanation: All duplicates — last is index 3.

Input: ([7], 7)

Expected Output: 0

Explanation: Single-element match.

Input: ([-3, -3, -1, 0], -3)

Expected Output: 1

Explanation: Rightmost -3 is at index 1.

Input: ([1, 1, 2, 3, 3, 3], 1)

Expected Output: 1

Explanation: Last 1 is at index 1.

Hints

  1. Symmetric to first-occurrence: record the match, then continue into the right half instead of the left.
  2. On nums[mid] == target, store mid and set lo = mid + 1. The 'equal' and 'less' branches both move lo right, so they can be merged.
  3. Because lo only ever increases and hi only ever decreases by at least one each iteration, the window strictly shrinks and the loop terminates when lo > hi.

Binary Search — Insertion Index (Search Insert Position)

Given a sorted integer array `nums` (distinct or with duplicates) and a `target`, return the index where `target` is found, OR — if it is absent — the index at which it could be inserted to keep the array sorted. This is the classic lower-bound search. Do not use any library helpers. Use a half-open interval [lo, hi). When the loop ends, `lo` equals the number of elements strictly less than `target`, which is exactly the insertion point (and, if present, the index of the first occurrence). Example: nums = [1, 3, 5, 6], target = 5 -> 2 (present) nums = [1, 3, 5, 6], target = 2 -> 1 (insert before 3) nums = [1, 3, 5, 6], target = 7 -> 4 (append at end)

Constraints

  • 0 <= len(nums) <= 10^5
  • nums is sorted in non-decreasing order
  • -10^9 <= nums[i], target <= 10^9
  • Do not use any built-in search helpers

Examples

Input: ([1, 3, 5, 6], 5)

Expected Output: 2

Explanation: 5 is present at index 2.

Input: ([1, 3, 5, 6], 2)

Expected Output: 1

Explanation: 2 would be inserted at index 1, between 1 and 3.

Input: ([1, 3, 5, 6], 7)

Expected Output: 4

Explanation: 7 is larger than all, appended at index 4.

Input: ([1, 3, 5, 6], 0)

Expected Output: 0

Explanation: 0 is smaller than all, inserted at index 0.

Input: ([1, 3, 5, 6], 4)

Expected Output: 2

Explanation: 4 would be inserted at index 2.

Input: ([], 5)

Expected Output: 0

Explanation: Empty array — insert at index 0.

Input: ([2, 2, 2], 2)

Expected Output: 0

Explanation: Lower bound of all-duplicates is index 0.

Input: ([-5, -2, 0, 3], -3)

Expected Output: 1

Explanation: -3 inserts between -5 and -2 at index 1.

Hints

  1. Use a half-open window [lo, hi) with hi initialized to len(nums), not len(nums) - 1. Invariant: every index < lo has value < target, every index >= hi has value >= target.
  2. When nums[mid] < target, move lo = mid + 1; otherwise keep mid as a candidate with hi = mid (do NOT use mid - 1 here).
  3. The loop ends when lo == hi; that common value is the lower bound — the first position whose value is >= target, i.e. the insertion point (and the first-occurrence index if target is present).
Last updated: Jun 25, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Deep Equality of Two Records - Uber (medium)
  • Shortest Path in a Grid with Blocked Cells - Uber (medium)
  • Reconstruct the Alphabet Order of an Alien Language - Uber (medium)
  • Design and Implement an LRU Cache - Uber (medium)
  • Maximize Throughput and Count Trigger Components - Uber (medium)