Array#bsearch

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

Returns: Object or nil · Added in v2.0 · Updated March 14, 2026 · Array Methods

ruby array binary-search searching algorithm

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.

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)

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>

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

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!

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