AlgoThrive
← All searching algorithms

Binary Search

CheckingRuled outFound

array

target = 15
2
4
6
9
12
15
18
20
0lo
1
2
3
4
5
6
7hi

pseudocode

binarySearch(a, target)
  lo = 0; hi = n - 1
  while lo <= hi
    mid = (lo + hi) / 2
    if a[mid] == target return mid
    if a[mid] < target then lo = mid + 1
    else hi = mid - 1
  return -1

Frame 1 / 5

Looking for 15 in a sorted array

lo = 0, hi = 7

4

Pick a value that is in the array — or one that isn't, to watch the search fail.

3–16 integers between 1 and 20 — the array is sorted for you, because binary search needs ordered data.