|Binary Search
All Challenges

Binary Search

HardSearching

Given a sorted list of integers arr and a target integer target, return the index of target in the list.


If the target is not in the list, return -1.


Do not use Python's built-in `index()` or `in` operator — implement the binary search algorithm yourself.


Binary search is O(log n) — searching a million records takes at most 20 comparisons. It powers database indexes, dictionary lookups, and version control diffing.

Examples

Input: binary_search([1, 2, 3, 4, 5], 3)
Output: 2
Target at index 2
Input: binary_search([1, 2, 3, 4, 5], 6)
Output: -1
Not found
Input: binary_search([-5, 0, 3, 9, 12], 9)
Output: 3
Target at index 3
Input: binary_search([1], 1)
Output: 0
Single element, found

Constraints

  • 0 <= len(arr) <= 100,000
  • arr is sorted in ascending order with no duplicates
  • Do not use .index() or the in operator
pythoneditor
Loading Python runtime…