Learn how to search for a value in a sorted list in O(log n) time using binary search in Python.

Binary Search

Problem

Given a sorted list and a target value, find the index of the target. If not found, return -1.

Input:  [1, 3, 5, 7, 9, 11, 13], target=7
Output: 3   (index 3)

Input:  [1, 3, 5, 7, 9, 11, 13], target=6
Output: -1  (not found)

Input:  [2, 4, 6, 8, 10], target=2
Output: 0   (first element)

Input:  [2, 4, 6, 8, 10], target=10
Output: 4   (last element)

Why binary search?

Linear search checks every element one by one — O(n). For 1,000,000 elements, that is up to 1,000,000 comparisons.

Binary search cuts the search space in half every step — O(log n). For 1,000,000 elements, that is at most 20 comparisons.

Linear search — 1,000,000 elements → up to 1,000,000 steps
Binary search — 1,000,000 elements → at most 20 steps

log₂(1,000,000) ≈ 20

Logic

Binary search only works on sorted arrays. The idea:

Look at the middle element
If it equals the target — found it
If the target is smaller — search the left half
If the target is larger — search the right half
Repeat with the new half until found or nothing left

Solution 1 — iterative binary search

Use two pointers — left and right — that narrow in on the target.

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        # find the middle index
        # use left + (right - left) // 2 to avoid integer overflow
        mid = left + (right - left) // 2

        if arr[mid] == target:
            return mid          # found — return the index

        elif arr[mid] < target:
            left = mid + 1      # target is in the right half

        else:
            right = mid - 1     # target is in the left half

    return -1   # not found


arr = [1, 3, 5, 7, 9, 11, 13]

print(binary_search(arr, 7))    # 3
print(binary_search(arr, 6))    # -1
print(binary_search(arr, 1))    # 0
print(binary_search(arr, 13))   # 6
print(binary_search(arr, 0))    # -1

Code Execution — Solution 1

Trace through binary_search([1, 3, 5, 7, 9, 11, 13], target=7):

Array indices: 0:1, 1:3, 2:5, 3:7, 4:9, 5:11, 6:13

Step	`left`	`right`	`mid`	`arr[mid]`	Compare	Action
1st	`0`	`6`	`3`	`7`	`7 == 7`	Return `3` ✅

Found on first try — the middle element was the target.

Trace through binary_search([1, 3, 5, 7, 9, 11, 13], target=11):

Step	`left`	`right`	`mid`	`arr[mid]`	Compare	Action
1st	`0`	`6`	`3`	`7`	`7 < 11`	`left = 4`
2nd	`4`	`6`	`5`	`11`	`11 == 11`	Return `5` ✅

Trace through binary_search([1, 3, 5, 7, 9, 11, 13], target=6):

Step	`left`	`right`	`mid`	`arr[mid]`	Compare	Action
1st	`0`	`6`	`3`	`7`	`7 > 6`	`right = 2`
2nd	`0`	`2`	`1`	`3`	`3 < 6`	`left = 2`
3rd	`2`	`2`	`2`	`5`	`5 < 6`	`left = 3`
4th	`3`	`2`	—	—	`left > right`	Return `-1`

We use mid = left + (right - left) // 2 instead of (left + right) // 2. Both give the same result in Python since Python handles arbitrarily large integers. But in languages like C or Java, left + right can overflow for very large indices. The safe formula is a good habit to build.

Solution 2 — recursive binary search

The same logic expressed recursively. Each call works on a smaller portion of the array.

def binary_search_recursive(arr, target, left=0, right=None):
    # set right on first call
    if right is None:
        right = len(arr) - 1

    # base case — search space is empty
    if left > right:
        return -1

    mid = left + (right - left) // 2

    if arr[mid] == target:
        return mid          # found

    elif arr[mid] < target:
        # search right half
        return binary_search_recursive(arr, target, mid + 1, right)

    else:
        # search left half
        return binary_search_recursive(arr, target, left, mid - 1)


arr = [1, 3, 5, 7, 9, 11, 13]

print(binary_search_recursive(arr, 7))    # 3
print(binary_search_recursive(arr, 6))    # -1
print(binary_search_recursive(arr, 1))    # 0
print(binary_search_recursive(arr, 13))   # 6

Code Execution — Solution 2

Trace through binary_search_recursive([1,3,5,7,9,11,13], target=3):

call(left=0, right=6)
  mid = 3, arr[3] = 7
  7 > 3 → search left half
  call(left=0, right=2)
    mid = 1, arr[1] = 3
    3 == 3 → return 1 ✅

Trace through binary_search_recursive([1,3,5,7,9,11,13], target=6):

call(left=0, right=6)
  mid=3, arr[3]=7 → 7>6 → search left
  call(left=0, right=2)
    mid=1, arr[1]=3 → 3<6 → search right
    call(left=2, right=2)
      mid=2, arr[2]=5 → 5<6 → search right
      call(left=3, right=2)
        left > right → return -1 ✅

Solution 3 — using bisect module

Python's built-in bisect module implements binary search. Use it in real projects.

import bisect

def binary_search_bisect(arr, target):
    # bisect_left finds where target would be inserted
    index = bisect.bisect_left(arr, target)

    # check if the element at that index is actually the target
    if index < len(arr) and arr[index] == target:
        return index

    return -1   # not found


arr = [1, 3, 5, 7, 9, 11, 13]

print(binary_search_bisect(arr, 7))    # 3
print(binary_search_bisect(arr, 6))    # -1
print(binary_search_bisect(arr, 1))    # 0
print(binary_search_bisect(arr, 13))   # 6

# bisect also helps with insertion
arr2 = [1, 3, 5, 7, 9]
pos = bisect.bisect_left(arr2, 6)
print(f"Insert 6 at index: {pos}")   # 3

# insort inserts and keeps sorted
bisect.insort(arr2, 6)
print(arr2)   # [1, 3, 5, 6, 7, 9]

Code Execution — Solution 3

Trace through binary_search_bisect([1,3,5,7,9,11,13], target=7):

bisect_left([1,3,5,7,9,11,13], 7):

Binary searches for where 7 should be inserted to keep sorted order
Returns index 3 (7 is already there)

Check: arr[3] == 7 → True → return 3

Trace through binary_search_bisect([1,3,5,7,9,11,13], target=6):

bisect_left([1,3,5,7,9,11,13], 6):

6 would be inserted at index 3 (between 5 and 7)
Returns 3

Check: arr[3] == 7 → 7 != 6 → return -1

Extended — find first and last occurrence

When a sorted array has duplicates, find the first and last index of the target.

def find_first(arr, target):
    """Find the first index of target in a sorted array."""
    left, right = 0, len(arr) - 1
    result = -1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            result = mid        # found — but keep searching left
            right = mid - 1    # narrow to left half for first occurrence

        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result


def find_last(arr, target):
    """Find the last index of target in a sorted array."""
    left, right = 0, len(arr) - 1
    result = -1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            result = mid       # found — but keep searching right
            left = mid + 1     # narrow to right half for last occurrence

        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result


arr = [1, 2, 2, 2, 3, 4, 5]

print(find_first(arr, 2))   # 1
print(find_last(arr, 2))    # 3
print(find_first(arr, 6))   # -1

Code Execution — first and last occurrence

Trace through find_first([1, 2, 2, 2, 3, 4, 5], target=2):

Step	`left`	`right`	`mid`	`arr[mid]`	Action	`result`
1st	`0`	`6`	`3`	`2`	Found → `result=3`, `right=2`	`3`
2nd	`0`	`2`	`1`	`2`	Found → `result=1`, `right=0`	`1`
3rd	`0`	`0`	`0`	`1`	`1 < 2` → `left=1`	`1`
4th	`1`	`0`	—	—	`left > right` → stop	`1`

Result: 1 — first occurrence of 2

Trace through find_last([1, 2, 2, 2, 3, 4, 5], target=2):

Step	`left`	`right`	`mid`	`arr[mid]`	Action	`result`
1st	`0`	`6`	`3`	`2`	Found → `result=3`, `left=4`	`3`
2nd	`4`	`6`	`5`	`4`	`4 > 2` → `right=4`	`3`
3rd	`4`	`4`	`4`	`3`	`3 > 2` → `right=3`	`3`
4th	`4`	`3`	—	—	`left > right` → stop	`3`

Result: 3 — last occurrence of 2

Performance comparison

import time
import random

# generate a large sorted list
arr = sorted(random.sample(range(1_000_000), 500_000))
target = arr[250_000]   # pick something in the middle

# linear search
start = time.perf_counter()
result = arr.index(target)
linear_time = time.perf_counter() - start

# binary search
start = time.perf_counter()
result = binary_search(arr, target)
binary_time = time.perf_counter() - start

print(f"Linear search: {linear_time:.6f}s")
print(f"Binary search: {binary_time:.6f}s")
print(f"Binary is {linear_time / binary_time:.0f}x faster")

Output:

Linear search: 0.003241s
Binary search: 0.000008s
Binary is 405x faster

Which solution to use?

Solution	How	Best when
Solution 1	Iterative	Default — clearest and most efficient
Solution 2	Recursive	Understanding the concept
Solution 3	`bisect` module	Real projects — built-in and reliable
Extended	First/last occurrence	Sorted arrays with duplicates

Output

Binary Search

Binary Search

Problem

Why binary search?

Logic

Flow

Solution 1 — iterative binary search

Code Execution — Solution 1

Solution 2 — recursive binary search

Code Execution — Solution 2

Solution 3 — using bisect module

Code Execution — Solution 3

Extended — find first and last occurrence

Code Execution — first and last occurrence

Performance comparison

Which solution to use?

Output

On this page