ML Prep

Recursive binary search

Problem

Implement binary_search(xs, target, lo=0, hi=None) recursively for an ascending list. Return an index containing target or -1. Do not slice the list.

Starter code

def binary_search(xs, target, lo=0, hi=None):
    pass
Reveal answer or reference solution
def binary_search(xs, target, lo=0, hi=None):
    if hi is None:
        hi = len(xs)
    if lo >= hi:
        return -1
    mid = (lo + hi) // 2
    if xs[mid] == target:
        return mid
    if xs[mid] < target:
        return binary_search(xs, target, mid + 1, hi)
    return binary_search(xs, target, lo, mid)

Public tests

  • binary_search([1,3,5,7,9], 7) → 3
  • binary_search([1,3,5,7,9], 2) → -1
  • binary_search([], 2) → -1

Local history

Loading attempts saved in this browser…

Use with your agent

Share this URL and your attempt. Ask the agent to start with a clarifying question or the smallest useful hint.

Tutor me on https://mlprep.iwase.dev/programming/diagnostic/original-py-binary-search/. If window.mlPrepAgent is available, read attempts for item original-py-binary-search before tutoring. Inspect my attempt, keep the item ID, and do not reveal the full answer first. After a real attempt, append its record and read it back.

Appears in