Algorithm Guidecomplexity: O(log n)

Binary Search

A very fast, high-performance search over a sorted array that repeatedly compares the middle value to halve the search range. Each iteration shrinks the candidate space by half, finding the value in a logarithmic number of comparisons.

01Binary Search

Explore How It Works

Starting binary search. Compare against the middle of the sorted array and cut the candidate range in half each time. Each node of the tree is one comparison.

The value in the middle of the range is 34. Compare it with the target 45.

34 is smaller than 45. The left half can be ignored, leaving only the four slots on the right.

The middle of what remains is 56. Compare it with the target again.

56 is larger than 45. This time the right side is dropped, leaving a single slot.

That last slot holds 45 — a match, after three comparisons.

Search complete · 45 sits at index 4. The left subtree was never looked at once.

Live Python

# target: 45

1def binary_search(arr, target):

# low: 0

2 low = 0

# high: 7

3 high = len(arr) - 1

4 while low <= high:

5 mid = (low + high) // 2

6 if arr[mid] == target:

7 return mid

8 elif arr[mid] < target:

9 low = mid + 1

10 else:

11 high = mid - 1

12 return -1

1 / 7

02 Understand It Simply

For Everyone

🔑How It Works

Compares against the middle of a sorted array and discards half the range each time.

💡In Plain Words

Compares against the middle of a sorted array and halves the search range each time.

Very fast at O(log n).

📍Where It's Used

–Searching sorted data
–finding boundary values

03 Python Implementation

A clean, readable reference implementation of the core logic of Binary Search.

core_implementation.py

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1