Binary Search in Ruby: Invariants Before Code

,

Binary search is fast because every comparison discards half of the remaining search space. The price of that speed is a strict precondition: the input must be sorted according to the same ordering used by the search.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def binary_search(values, target)
  left = 0
  right = values.length - 1

  while left <= right
    middle = left + (right - left) / 2
    comparison = values[middle] <=> target

    return middle if comparison.zero?

    if comparison.negative?
      left = middle + 1
    else
      right = middle - 1
    end
  end

  nil
end

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
binary_search(numbers, 5)  # => 4
binary_search(numbers, 42) # => nil

The invariant

At the start of every loop, if the target exists, it must be somewhere between left and right, inclusive. Each comparison preserves that invariant while shrinking the interval.

  • Time complexity: O(log n).
  • Space complexity: O(1) for the iterative version.

The old recursive version mixed a loop with recursive calls. It could work, but it paid for two control-flow mechanisms while needing only one. Algorithms are already hard enough; they do not need decorative recursion.

Ruby also provides Array#bsearch_index for production code:

1
numbers.bsearch_index { |value| value >= 5 } # => 4

Implement binary search to understand the invariant. Use the standard library when shipping software unless custom behavior is actually required.