← Searching & Arrays

Binary Search

Efficiently finds an element in a sorted array by halving the search space.

Target:11
1031527394115136157178

Step 1 of 7

Binary Search for target = 11 in a sorted array of 9 elements.

0
Comparisons
▶Algorithm
BinarySearch(arr, target):
lo = 0; hi = n−1
while lo ≤ hi:
mid = (lo + hi) / 2
if arr[mid] == target: return mid
if arr[mid] < target: lo = mid+1
else: hi = mid−1
return −1 // not found

Legend

Mid element
Search window
Found
Out of range
1 / 7Speed