Binary Search

easy Coding Interview Patterns 10–15 min

NumPy allowed · plain Python earns 10 bonus points

Interactive
Graph & Tree Traversal, Step by Step
Structure
Algorithm
ABCDE
visiting A -> visited order so far: [A]
queue now: [B, C]
Step 1 / 5
Both modes run the real algorithm from the linked practice problem, one step at a time -- edit the graph or pick different tree nodes and every step recomputes live.

Implement classic binary search from scratch -- the O(log n) algorithm every tree-height-bounded search, and half of this track's own name, is built on.

Related Skills

Task

Implement binary_search(nums, target): maintain a shrinking [lo, hi] window; at each step compare target to the midpoint and discard the half that cannot contain it.

Function Signature

binary_search(nums: list[int], target: int) -> int

Examples

Example 1: Target Present
Input: nums = [-1, 0, 3, 5, 9, 12] target = 9
Output: 4
Example 2: Target Absent
Input: nums = [-1, 0, 3, 5, 9, 12] target = 2
Output: -1

Constraints

  • Libraries (e.g. the bisect module) are allowed and accepted normally; A plain-Python solution earns 10 bonus points.
  • nums is sorted ascending with all distinct values.
  • Must run in O(log n) time -- a linear scan does not satisfy the intended solution, even though it would give a correct answer.
  • Return -1 if target is not present.
Python3Saved ✓
def binary_search(nums: list[int], target: int) -> int:
"""nums: a list sorted in ascending order, all distinct values.
Return the index of target in nums, or -1 if it is not present.
Must run in O(log n) time."""
# Your implementation here
pass

Case 1: Target Present
Input: nums = [-1, 0, 3, 5, 9, 12] target = 9
Expected: 4
Case 2: Target Absent
Input: nums = [-1, 0, 3, 5, 9, 12] target = 2
Expected: -1