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 "shellwords"
require "open3"
 
module Backup

Building safe shell commands in Ruby

shell-out subprocess command-injection
Intermediate 7 steps
ruby 
class UserAgentParser
  BROWSERS = [
    [/Edg\/([\d.]+)/, "Edge"],
    [/OPR\/([\d.]+)/, "Opera"],

Parsing user-agent strings in Ruby

regex pattern-matching lookup-tables
Intermediate 8 steps
ruby 
class LogAggregator
  BUCKET_FORMAT = "%Y-%m-%dT%H:%M"
 
  def initialize(entries)

Bucketing log entries by the minute in Ruby

aggregation hashing enumerable
Intermediate 5 steps
ruby 
class WeeklySignupsReport
  DEFAULT_WEEKS = 12
 
  def initialize(weeks: DEFAULT_WEEKS, source: User.all)

Building a weekly signups report in Rails

service object aggregation group by
Intermediate 7 steps
ruby 
class ApplicationController < ActionController::Base
  EXPERIMENTS = {
    checkout_button_color: %w[control blue green],
    onboarding_flow: %w[control streamlined]

How A/B test cohorts are assigned in Rails

a-b-testing cookies hashing
Intermediate 8 steps
ruby 
class SnippetHighlighter
  CONTEXT_RADIUS = 60
  MAX_TERMS = 8
 

Building search-result snippets in Ruby

regular-expressions text-processing search
Intermediate 9 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