Array#bsearch

Updated April 1, 2026 · Array Methods

ruby array bsearch binary-search stdlib

What does `bsearch` do?

bsearch performs a binary search on a sorted array to find an element or the smallest element that satisfies a condition. Unlike linear search methods that check every element, bsearch halves the search space on each iteration, making it dramatically faster for large sorted arrays.

Array#bsearch is defined directly on the Array class but behaves identically to Enumerable#bsearch — Array includes Enumerable, and Array overrides bsearch with an optimised implementation.

Basic Usage

Find minimum mode (find-min)

In find-minimum mode, the block returns a comparison: 0 when the current element matches, a negative number when the element is less than the target, or a positive number when the element is greater than the target.

The method returns the first element for which the block returns 0:

# Array must be sorted in ascending order
sorted = [1, 3, 5, 7, 9, 11, 13, 15]

# Find the first element >= 7
sorted.bsearch { |n| n >= 7 }   # => 7

# Find the exact element 11
sorted.bsearch { |n| 11 <=> n }  # => 11

# Find first element > 10
sorted.bsearch { |n| n > 10 }    # => 11

Find any mode (find-any)

In find-any mode, the block returns -1, 0, or 1 explicitly:

-1 — element is less than target (search right half)
0 — element matches (return this element)
1 — element is greater than target (search left half)

sorted = [1, 3, 5, 7, 9, 11, 13, 15]

# Find exact match
sorted.bsearch { |n| 9 <=> n }   # => 9

# Find any element in a range
sorted.bsearch { |n| [5, 6, 7].include?(n) ? 0 : n <=> 5 }
# => 5

Without a block

When called without a block, bsearch returns an Enumerator:

[1, 3, 5, 7].bsearch  # => #<Enumerator: [1, 3, 5, 7]:bsearch>

This is rarely useful for bsearch since you need the block to define the search condition, but it allows method chaining:

[1, 3, 5, 7].bsearch.lazy  # => #<Enumerator::Lazy: #<Enumerator: [1, 3, 5, 7]:bsearch>:bsearch>

Critical Requirement: The Array Must Be Sorted

bsearch produces undefined results if the array is not sorted in ascending order. Ruby does not validate this — it assumes you know what you’re doing:

# Unsorted array — bsearch returns garbage
unsorted = [3, 1, 4, 1, 5, 9, 2, 6]
unsorted.bsearch { |n| n >= 4 }   # => unpredictable (possibly 4, 5, 9, or wrong)

If the array is not sorted, use a linear search instead:

# Sort first, then bsearch
unsorted.sort.bsearch { |n| n >= 4 }  # => 4

The array must be sorted in ascending order (smallest to largest). Descending order or partial sorting will not work correctly.

`bsearch` vs `find` / `index`

Method	Search Type	Time Complexity	Use When
`bsearch`	Binary search	O(log n)	Array is sorted
`find` / `detect`	Linear search	O(n)	Array is unsorted, find first match
`index`	Linear search	O(n)	Need the position of an element

Example comparison

large = (1..1_000_000).to_a

# bsearch: ~20 comparisons max (log2 1_000_000 ≈ 20)
large.bsearch { |n| n >= 500_000 }   # => 500000

# find: could check up to 500,000 elements
large.find { |n| n >= 500_000 }       # => 500000

For a million-element array, bsearch needs at most 20 comparisons, while find might need up to 500,000.

Practical Examples

Finding a price range

# Product prices sorted for range queries
prices = [
  { min: 0, max: 50, label: "Budget" },
  { min: 50, max: 200, label: "Mid-range" },
  { min: 200, max: 1000, label: "Premium" }
]

# Find which price range $175 falls into
prices.bsearch { |p| p[:max] <=> 175 }  # => nil (edge case)
prices.bsearch { |p| 175 <=> p[:min] }  # => { min: 50, max: 200, label: "Mid-range" }

# For $250
prices.bsearch { |p| 250 <=> p[:min] }  # => { min: 200, max: 1000, label: "Premium" }

Version lookup

# Ruby version requirements for gems
version_requirements = [
  { version: "2.7", features: ["argument forwarding", "endless method definition"] },
  { version: "3.0", features: ["pattern matching", "ractor"] },
  { version: "3.1", features: ["hash values omission", "enumerate"] },
  { version: "3.2", features: ["pattern matching refinement", "Regexp timeout"] }
]

# Find the first version that supports Ruby 3.1+
version_requirements.bsearch { |req| Gem::Version.new(req[:version]) <=> Gem::Version.new("3.1") }
# => { version: "3.1", features: ["pattern matching refinement", "...] }

# Find which version introduced a specific feature
version_requirements.bsearch { |req| req[:features].include?("pattern matching") ? 0 : 1 <=> 0 }
# => { version: "3.0", features: ["pattern matching", "ractor"] }

Finding by index (simulating bsearch_index)

Ruby doesn’t have a separate bsearch_index method in older versions, but you can return the index:

sorted = ["apple", "banana", "cherry", "date", "elderberry"]

# Find the index of an element
index = sorted.bsearch_index { |s| "cherry" <=> s }
index  # => 2

# Or with find-minimum mode
index = sorted.bsearch_index { |s| s <=> "cherry" }
index  # => 2

# Using the index
sorted[index]  # => "cherry"

If you need both the element and index:

sorted = [10, 20, 30, 40, 50]

element = sorted.bsearch { |n| n <=> 30 }
index = sorted.index(element)

element  # => 30
index    # => 2

Edge Cases

No match returns nil

[1, 3, 5, 7, 9].bsearch { |n| n > 10 }   # => nil
[1, 3, 5, 7, 9].bsearch { |n| n >= 10 }  # => nil

Empty array returns nil

[].bsearch { |n| n > 0 }   # => nil

Single element array

[42].bsearch { |n| n <=> 42 }   # => 42
[42].bsearch { |n| n <=> 10 }   # => nil

Duplicate elements

bsearch returns the leftmost element that satisfies the condition:

sorted = [1, 3, 5, 5, 5, 7, 9]

# Find first element >= 5 (returns the first 5)
sorted.bsearch { |n| n >= 5 }   # => 5

Finding all elements in a range (not supported directly)

bsearch returns only the first match. To find all elements in a range, use two searches:

sorted = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# Find all elements between 4 and 7
low = sorted.bsearch { |n| n >= 4 }   # => 4
high = sorted.bsearch { |n| n > 7 }    # => 8

# Get the range
range_start = sorted.index(low)        # => 3
range_end = sorted.index(high)         # => 7

sorted[range_start...range_end]        # => [4, 5, 6, 7]

Performance Notes

bsearch has O(log n) time complexity — the number of comparisons grows logarithmically with the array size:

Array Size	Linear Search (worst)	Binary Search (worst)
100	100 comparisons	7 comparisons
1,000	1,000 comparisons	10 comparisons
1,000,000	1,000,000 comparisons	20 comparisons
1,000,000,000	1,000,000,000 comparisons	30 comparisons

When to use bsearch

Use bsearch when:

The array is already sorted (or can be sorted once for many lookups)
You need to perform many lookups on the same data
Performance matters for large datasets

Stick with find or select when:

The array is unsorted and sorting would be expensive
You need all matching elements (bsearch returns only the first)
The array is small and the overhead of binary search isn’t worth it

Memory usage

bsearch is memory-efficient — it doesn’t allocate new arrays, just returns a reference to the found element. This is O(1) extra space.

What does bsearch do?