Codacoda
Back to Academy

searching

Binary Search

Binary Search finds the position of a target value within a sorted array by repeatedly dividing the search interval in half. It compares the target value to the middle element and eliminates half of the remaining elements each step.

Use Cases

  • •Searching in sorted arrays or lists
  • •Dictionary lookups and autocomplete
  • •Finding boundaries (lower/upper bound) in sorted data

Complexity Analysis

MetricBestAverageWorst
TimeO(1)O(log n)O(log n)
SpaceO(1)

Visualization

Target: 23
2
0
5
1
8
2
12
3
16
4
23
5
38
6
56
7
72
8
91
9
Speed:1x
Searching for 23 in sorted arrayStep 1 / 7

Implementation

Output

Click "Run Code" to see output...