Binary Search, Recursively

Medium ⏱ 12 min 62% acceptance ★★★★☆ 4.3
Implement binary_search(arr, target) on a sorted list of ints, returning the index of target, or -1 if it is absent. Solve it with recursive divide-and-conquer — no loops.

Examples

Example 1
Input
binary_search([1,3,5,7,9,11], 7)
Output
3
Explanation

7 sits at index 3 of the sorted list.

Example 2
Input
binary_search([1,3,5,7,9,11], 4)
Output
-1
Explanation

4 is not present.

Constraints

  • arr is sorted ascending.
  • Solve recursively, not with a while loop.

Topics

RecursionSearching

Companies

AppleAtlassian

Hints

Hint 1

Track a lo/hi window, e.g. via a nested helper function.

Hint 2

Compare arr[mid] to target and recurse into the correct half.

← Fibonacci with a Memo Dictionary Flatten an Arbitrarily Nested List →
Loading the Python runtime… Run executes your code and shows printed output; Submit checks your function against this problem's examples.