Suggest an edit

Improve this article

Refine the answer for “Why is the algorithm called "binary"?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

The algorithm is called "binary" because at each step it makes a binary (two-way) choice or splits the solution space into two parts. This relies on binary logic (0/1, true/false) and often leads to base-2 logarithmic complexity, as in binary search.

## Detailed answer

### What "binary" means in algorithms

- "Binary" (from the Latin bi, "two") - the algorithm's key action comes down to choosing between two alternatives or splitting into two subsets.
- The decision is made using binary logic: yes/no, less/greater, fits/does not fit.
- Such algorithms often run in O(log2 n) because at each step they "consume" roughly half of the options, or one bit of information.

### Where this shows up

- Binary search: `n → n/2 → n/4 → …` - each comparison picks one of the two halves of the sorted array.
- Fast exponentiation (binary exponentiation): the exponent is represented in binary; for each bit, a "take/don't take" decision is made about the factor.
- Binary trees and heaps: each node has at most two children; operations follow one of two branches.
- Binary lifting: jumps by powers of two, 2^k, where decisions are built from the "bits" of the path length.

### Why this particular name

- Two outcomes per step: choosing the left or the right branch/half.
- Halving: the problem shrinks by roughly a factor of 2 per iteration.
- Reliance on binary representation: decisions/paths are encoded as bits, and complexity relates to the number of bits.

### Example: binary search (JavaScript)

A classic example of "binariness": at each comparison we choose one of the two halves of the sorted array. Below is the lower_bound variant (the first position where the element is not less than target).

1. We maintain the invariant of the half-open interval [l, r), where the answer always lies inside.
2. At each iteration we take the middle m and decide: go left or right.
3. We stop when l == r - that is the answer.

```javascript
// Binary search: position of the first element >= target (lower_bound)
function lowerBound(arr, target) {
  let l = 0, r = arr.length; // half-open interval [l, r)
  while (l < r) {
    const m = l + ((r - l) >> 1); // middle without risk of overflow
    if (arr[m] >= target) {
      r = m;          // the target is in the left half (including m)
    } else {
      l = m + 1;      // the target is in the right half (strictly after m)
    }
  }
  return l;           // index of the insertion point/first element >= target
}

// Example
const a = [1, 3, 5, 7, 9];
console.log(lowerBound(a, 6)); // 3 (element 7)
```

### Key properties and requirements of "binary" approaches

- Monotonicity is needed: the predicate must be true at one end of the range and false at the other (or the data must be sorted).
- Complexity is usually O(log2 n) in the number of steps; memory is O(1) in iterative form.
- It is important to correctly maintain the boundary invariants and handle duplicates/empty arrays/out-of-range access.

### How "binary" differs from other approaches

- Ternary search splits the range into three parts; binary search splits it into two.
- Interpolation search picks a position by estimation rather than necessarily the middle; it is not "binary".
- "Binary" does not necessarily mean bitwise operations - it refers to a binary choice/a binary structure of the step.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts577 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.