Array#bsearch

arr.bsearch { |x| block } -> obj or nil

Returns Object or nil· Added in v2.0· Updated May 30, 2026· Array Methods

rubyarraybinary-searchsearchingalgorithm

Array#bsearch performs a binary search on a sorted array, finding an element that matches a condition you define in a block. Unlike linear search which scans each element, binary search halves the search space each iteration, making it dramatically faster for large arrays — O(log n) instead of O(n).

The catch: your array must be sorted in ascending order, and your block must return a condition that establishes a “find me the boundary” predicate.

Syntax

array.bsearch { |element| block }
array.bsearch  # without block returns an Enumerator

When called without a block, bsearch returns an Enumerator that you can chain or iterate over.

How the block works

The block must return a boolean or truthy/falsy value. Ruby interprets the return value as a “mode” switch:

Find minimum mode: Block returns true for elements that satisfy your condition, and false for those that do not. The search finds the first such element.
Find any mode: Block returns a number. Negative means “look left”, zero means “found!”, positive means “look right”.

For most use cases, use the find minimum mode — it is simpler and does what you would expect.

Return Value

Returns the first element where the block returns true
Returns nil if no element satisfies the condition
In “find any” mode, returns a matching element or nil

Examples

Find minimum mode (most common)

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

# Find the first number >= 8
numbers.bsearch { |x| x >= 8 }
# => 9

The block says “true when x >= 8”. The first element satisfying this is 9.

The find-minimum mode is the one you will reach for most often because it mirrors how you naturally think about searching: “give me the first element that meets this threshold.” Once you understand that the block returns a boolean and that true means “this element and everything after it is a candidate,” the behaviour clicks.

Finding exact values in a sorted range

prices = [10, 25, 40, 55, 70, 85, 100]

# Find the price at exactly 55
prices.bsearch { |x| x >= 55 }
# => 55

# Find the price just below 60
prices.bsearch { |x| x >= 60 }
# => 70 (first price >= 60)

When you search for an exact value that exists in the array, the block condition x >= 55 returns the element itself because 55 is the first value that satisfies the threshold. When the exact value is missing, the search returns the next larger element, which is the insertion point behaviour that makes binary search useful for sorted collections.

Working with objects

require "date"

events = [
  Date.new(2024, 1, 15),
  Date.new(2024, 3, 22),
  Date.new(2024, 6, 10),
  Date.new(2024, 9, 5),
  Date.new(2024, 12, 1)
]

# Find first event on or after July 1
target = Date.new(2024, 7, 1)
events.bsearch { |d| d >= target }
# => #<Date 2024-09-05>

Binary search works on any ordered collection, not just numbers. As long as your objects implement <=> (the spaceship operator) and the array is sorted accordingly, bsearch can find dates, strings, version numbers, or custom value objects. The block just needs to compare elements using the same ordering that sorted the collection.

Find any mode (less common)

In “find any” mode, your block returns a number:

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

# Find element 5 using comparison result
sorted.bsearch { |x| 5 - x }
# => 5

Here, for element 5: 5 - 5 = 0 means “found!”. For elements less than 5, the result is negative (search left). For greater elements, positive (search right).

The find-any mode is more flexible but also more error-prone because the block return value drives the search direction. A negative result tells Ruby to look in the left half, zero means the current element is a match, and a positive result means look right. Most of the time, find-minimum mode is clearer and does what you need.

Using with ranges

# Find a value within a range
range = (0..1000)
result = (0..1000).bsearch { |x| x*x >= 100 }
# => 10

This finds the square root of 100 using binary search on the range!

Ranges respond to bsearch too, which opens up a clever pattern for numeric root-finding and threshold calculations. Because a range is already ordered, you can search it directly without materialising a large array, keeping the memory cost at O(1) while still getting the O(log n) lookup speed.

Error cases

# Array must be sorted — bsearch does NOT sort for you
[3, 1, 2].bsearch { |x| x >= 2 }
# => nil or unexpected result (unsorted!)

# Empty array returns nil
[].bsearch { |x| x > 0 }
# => nil

Performance

Method	Time Complexity	Best For
`.bsearch`	O(log n)	Large sorted arrays
`.find` / `.detect`	O(n)	Small arrays or unsorted
`.index`	O(n)	Unsorted, exact match

For an array of 1 million elements, bsearch takes about 20 comparisons vs. 500,000 for linear search.

Common Mistakes

Forgetting the array is sorted: Binary search only works on sorted arrays. If your data is not sorted, sort it first or use find.
Wrong block logic: Make sure your block returns true for elements you are looking FOR, not elements to skip.
Using with descending order: Array must be ascending. Reverse it first if needed.

# Wrong: descending order gives wrong results
[10, 8, 6, 4, 2].bsearch { |x| x <= 6 }
# => unpredictable

# Correct: sort ascending first
[10, 8, 6, 4, 2].sort.reverse.bsearch { |x| x <= 6 }
# => 6