Binary Search

searching

Click Generate New or press Play

Step 1 / 1

Ready

Speed

Efficiently searches a sorted array by repeatedly dividing the search interval in half.

Time Complexity

Best

\mathrm{O}\left(1\right)

Avg

\mathrm{O}\left(\log n\right)

Worst

\mathrm{O}\left(\log n\right)

Max Operations

Worst-case bound

\lfloor \log_2(n) \rfloor + 1

Used for efficiency calculation in Stats Panel

Space Complexity

Aux

\mathrm{O}\left(1\right)

Iterative — low/high/mid pointers only

Pseudocode

1procedure binarySearch(A, target)

2low = 0, high = n-1

3mid = (low+high)/2

4if A[mid] == target: return mid

5if A[mid] < target: low = mid+1

6if A[mid] > target: high = mid-1

7while low <= high: repeat

8return NOT_FOUND