ruby 39 lines · 7 steps

Binary search patterns with Ruby's bsearch

Build lower bound, upper bound, count, and predicate search on top of Array#bsearch's two modes.

Explained by highlit
Intermediate binary-search algorithms ranges blocks monotonic-predicate
1# Binary search using Ruby's built-in Array#bsearch.
2#
3# There are two modes:
4# 1. find-minimum mode -> block returns true/false (monotonic)
5# 2. find-any mode -> block returns negative / zero / positive
6 
7module BinarySearch
8 module_function
9 
10 # Find the value exactly equal to target, or nil if absent.
11 # Uses find-any mode: the block compares like the spaceship operator.
12 def find_equal(sorted, target)
13 sorted.bsearch { |x| target <=> x }
14 end
15 
16 # Find the index of the first element >= target (lower bound).
17 # Uses find-minimum mode on indices: block must be monotonic false..true.
18 def lower_bound(sorted, target)
19 (0...sorted.size).bsearch { |i| sorted[i] >= target }
20 end
21 
22 # Find the index of the first element > target (upper bound).
23 def upper_bound(sorted, target)
24 (0...sorted.size).bsearch { |i| sorted[i] > target }
25 end
26 
27 # Count occurrences of target in a sorted array.
28 def count(sorted, target)
29 lo = lower_bound(sorted, target)
30 return 0 if lo.nil? || sorted[lo] != target
31 hi = upper_bound(sorted, target) || sorted.size
32 hi - lo
33 end
34 
35 # Smallest integer x in [lo, hi] such that the predicate holds.
36 def first_true(lo, hi, &pred)
37 (lo..hi).bsearch(&pred)
38 end
39end
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1bsearch has two modes: a spaceship-style comparison for exact finds and a monotonic true/false predicate for boundary finds.
  2. 2Searching over an index range instead of values lets you return positions, which is what lower/upper bound need.
  3. 3Once you have lower and upper bound, range-based queries like counting occurrences fall out almost for free.

Related explainers

ruby 
require "csv"
 
class SalesReport
  def initialize(path)

Aggregating CSV sales data in Ruby

data-aggregation memoization group_by
Intermediate 6 steps
ruby 
module DurationFormatter
  UNITS = [
    ['week', 604_800],
    ['day', 86_400],

Turning seconds into human-readable durations in Ruby

greedy-decomposition modular-arithmetic formatting
Intermediate 7 steps
ruby 
class Comment < ApplicationRecord
  belongs_to :post
  belongs_to :author, class_name: "User"
 

Live-updating comments with Turbo in Rails

turbo-streams callbacks associations
Intermediate 8 steps
ruby 
require 'json'
require 'set'
 
class SensitiveScrubber

Recursively scrubbing secrets from JSON

recursion data-masking pattern-matching
Intermediate 7 steps
ruby 
class ReportBatcher
  BATCH_SIZE = 500
 
  def initialize(account)

Batching monthly email summaries in Rails

batching service-object background-jobs
Intermediate 7 steps
ruby 
class Comment < ApplicationRecord
  belongs_to :commentable, polymorphic: true, counter_cache: true
  belongs_to :author, class_name: "User"
 

How polymorphic comments work in Rails

polymorphic-association concerns counter-cache
Intermediate 8 steps

Share this explainer

Here's the card — post it anywhere.

Binary search patterns with Ruby's bsearch — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code