Array#bsearch

Updated May 30, 2026· Array Methods

rubyarraybsearchbinary-searchstdlib

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. Unlike each or map, calling bsearch without a block is an unusual pattern because the method has no default search condition to fall back on. The enumerator itself is inert until you chain it with another method or pass it to a block-accepting consumer, at which point the binary search logic executes with the comparator you provide.

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

The returned enumerator is rarely used on its own because bsearch requires a comparison block to produce meaningful results, but it does support method chaining when you want to defer the search or combine it with lazy enumeration. For instance, wrapping bsearch with .lazy lets you treat the binary search as one step in a larger lazy pipeline without evaluating the array until a terminal method is called.

[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 are doing. The binary search algorithm relies on the invariant that all elements to the left of the midpoint are smaller and all elements to the right are larger; when that invariant does not hold, each step of the search may eliminate the wrong half of the remaining elements, leading to a result that is essentially random with respect to the search condition.

# 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)

Binary search works by repeatedly guessing the middle of the remaining range and eliminating half of the remaining elements based on the comparison result. When the array is not sorted, the assumption that elements to the left of the midpoint are smaller and elements to the right are larger breaks down completely. The method still runs to completion but the item it lands on is essentially random, determined by the original unsorted order rather than by the search condition. If the array is not sorted, sort it first or 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

Choosing between these methods comes down to one question: is the array already sorted? If it is, bsearch is almost always the right pick for single-element lookups. If it is not, the cost of sorting first may outweigh the benefit of binary search, especially for one-off queries. For repeated lookups on the same data, the upfront sort cost amortises quickly, making bsearch the clear winner even when the array starts unsorted.

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. The gap widens as the array grows: at ten million elements, bsearch uses about 24 comparisons while find might examine five million. This is not just a theoretical difference; on large sorted datasets, bsearch can turn a multi-second linear scan into a sub-millisecond lookup, making it practical to perform searches that would otherwise require a database index or a specialised data structure.

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" }

The price range example shows that bsearch works on collections of any object type, not just numbers. The block extracts a numeric field from each entry and compares against the target value, and Ruby’s binary search logic operates on the comparison results without caring what the array elements actually contain. This pattern generalises to any ordered data: timestamps, scores, geographic coordinates, or any other comparable attribute stored in a sorted collection.

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 does not have a separate bsearch_index method in older versions, but you can return the index. The bsearch_index method was added in Ruby 2.3 and works identically to bsearch except that it returns the position of the found element rather than the element itself. When your target Ruby version supports it, bsearch_index is the cleaner choice for index-based lookups because it avoids the extra O(n) index call that would otherwise be needed to recover the position from the element.

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"

The bsearch_index method was added in Ruby 2.3 and returns the index of the found element rather than the element itself. When you have access to bsearch_index, using it directly is cleaner than calling bsearch followed by index because it avoids a second O(n) scan of the array. If your Ruby version predates 2.3 or you are writing code that targets a range of versions, the two-step pattern with bsearch and index provides a compatible fallback.

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

Getting both the element and its index requires two separate calls, which means the array is scanned twice: once by bsearch in O(log n) time and once by index in O(n) time. The index call is the expensive part because it walks the array linearly from the start. If you find yourself doing this often, consider keeping a separate index map or using an ordered data structure that maintains index information alongside the values, especially for large arrays where the O(n) penalty of index becomes noticeable.

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

When no element satisfies the block’s condition, bsearch returns nil rather than raising an exception or returning a sentinel value. This is the standard Ruby convention for “not found” and plays well with the safe navigation operator and conditional chaining. Always check the return value before using it as an index or passing it to another method that expects a real element.

Empty array returns nil

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

An empty array cannot contain any element, so bsearch returns nil regardless of what the block does. Ruby does not even call the block in this case because there are no elements to test. This follows the same logic as find and select on empty collections, and it means you do not need a separate guard for the empty case before calling bsearch.

Single element array

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

With a single-element array, the search is trivially O(1). Ruby tests the lone element against the block, and if it satisfies the condition the element is returned; otherwise nil is returned. This case handles correctly without any special-casing in your code, so the same bsearch call works for collections of any size, whether they are empty, contain a single element, or hold millions of entries.

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: one to locate the lower bound and another to locate the upper bound. The first search with n >= low finds the first element at or above the range start, and the second search with n > high finds the first element strictly above the range end. Slicing the array between these two positions yields all elements within the range.

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?