Binary Search

Difficulty: Easy · Topic: Searching

Given a sorted ascending array nums and a target, return the index of target if it exists, otherwise return -1. Aim for O(log n) time.

Examples

binary_search([-1,0,3,5,9,12], 9)
→ 4

nums[4] == 9.

binary_search([-1,0,3,5,9,12], 2)
→ -1

2 is not present.

binary_search([5], 5)
→ 0

Target complexity: time O(log n), space O(1)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.