Binary Search

DSA · Arrays and Searching

Theory

Binary search finds a target in a sorted array by repeatedly halving the search range. It compares the target with the middle element: if smaller, it searches the left half; if larger, the right half. Because the range halves every step, it needs at most about log₂(n) comparisons, so one million items need only around 20 steps. The same idea applies to any monotonic condition, such as finding the smallest valid capacity.

Why we use it

It turns O(n) searching into O(log n), which is dramatically faster for large sorted data.

When to use it

Use it on sorted arrays, for "first/last position" problems, and for "binary search on the answer" problems where you can test whether a value works.

How it works

  1. Start: low = 0, high = n - 1 (array is sorted)
  2. Is low <= high? Yes: mid = (low + high) // 2. No: Return -1 (not found).
  3. arr[mid] == target? Yes: Return mid (found). No: Compare target with arr[mid].
  4. target < arr[mid]? Yes: high = mid - 1 (search left half). No: low = mid + 1 (search right half).
  5. Repeat with the smaller range

Syntax

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

Time: O(log n)   Space: O(1)   Requires sorted data

Example

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

data = list(range(0, 1000000, 3))
print("Index and steps:", binary_search(data, 299997))
print("Missing value:", binary_search(data, 10))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic