DATA STRUCTURES • ALGORITHMS

Binary Search

An efficient search algorithm that works on sorted arrays by repeatedly dividing the search interval in half.

Time

O(log N)

Space

O(1)

Key Principle 1

Requires sorted input

Key Principle 2

Divide and conquer strategy

Key Principle 3

Significantly faster than linear search

Key Principle 4

Uses low, mid, and high pointers

BINARY_SEARCH_LAB
ARRAY:
Current Step
Binary Search for 70. Range: [0, 8]
Playback
Speed
Search Boundaries ⠿
LOW0
HIGH8
TARGET70
Binary Logic ⠿
1while (low <= high) {
2    int mid = low + (high - low) / 2;
3    if (arr[mid] == target) return mid;
4    if (arr[mid] < target) low = mid + 1;
5    else high = mid - 1;
6}
10
L
20
30
40
50
60
70
80
90
H

Loading Lab...