Skip to content
LEETFLIX

Binary Search

EasyArrayBinary search
Solve on LeetCode

Famous for being simple to describe and easy to get subtly wrong. Get the invariant right and the code writes itself.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Constraints

  • —1 <= nums.length <= 10^4
  • —-10^4 < nums[i], target < 10^4
  • —All the integers in nums are unique.
  • —nums is sorted in ascending order.

Examples

Input

nums =
[-1, 0, 3, 5, 9, 12]
target =
9

Output

4

nums

-1
0
0
1
3
2
5
3
9
4
12
5
found

9 exists in nums and its index is 4.

02

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

Iterative, closed interval [lo, hi]

Halve the candidate interval on every comparison until it's empty or the target is found.

Maintain [lo, hi] as the set of indices that could still hold target. Probe the middle: equal → done; smaller → discard the left half including mid; larger → discard the right half including mid.

Algorithm

  1. lo = 0, hi = n − 1.
  2. While lo <= hi: mid = lo + (hi − lo) // 2.
  3. If nums[mid] == target return mid.
  4. If nums[mid] < target: lo = mid + 1; else hi = mid − 1.
  5. Return -1.
Time
O(log n)
Space
O(1)
Solution.py
class Solution:    def search(self, nums: list[int], target: int) -> int:        lo, hi = 0, len(nums) - 1  # invariant: target ∈ nums[lo..hi] if present        while lo <= hi:            mid = lo + (hi - lo) // 2            if nums[mid] == target:                return mid            if nums[mid] < target:                lo = mid + 1  # mid is too small; discard it and everything left            else:                hi = mid - 1  # mid is too big; discard it and everything right        return -1
Watch this run

03

Interactive walkthrough

Playing “Iterative, closed interval [lo, hi]”. Edit the input, hit Run, then scrub.

Approach: Iterative, closed interval [lo, hi]

Loading animation…

Up next

#1Two Sum

Easy

Python · Go · Animated