skip to content

In Ruby, how does Array#bsearch's find-any mode work, and why must the block return target <=> element rather than element <=> target?

level: middleimportance: nice to knowfreq 15%

answer

  1. numeric block result selects it
  2. 0 means found
  3. positive: go right, negative: go left
  4. any matching element, not the first
  5. reversed <=> sends the search the wrong way

basics

~20 s

When the block returns numbers, bsearch runs in find-any mode: 0 means a match, positive means look further right, negative means look left. target <=> element has that sign; element <=> target is reversed and steers away from the target.

solid answer

~40 s

A numeric block result puts `bsearch` in **find-any** mode. The block reports where the target lies relative to the probed element: `0` for a match, a **positive** number when the target is further right, a **negative** number when it is further left. `target <=> element` has exactly those signs on an ascending array, so `a.bsearch { |x| 7 <=> x }` finds 7. The reversed `x <=> 7` returns `-1` for smaller elements, which tells the search to go left, so it can miss the target or return `nil`. Unlike find-minimum mode, find-any returns **some** matching element, not necessarily the first, which matters when the array holds duplicates. Its natural use is range-style matching, where the block returns 0 for a whole band of elements.

code

ruby · 11 lines
ruby
a = [0, 4, 7, 10, 12]

a.bsearch { |x| 4 <=> x }   # => 4, target on the left
a.bsearch { |x| x <=> 4 }   # => nil, signs reversed
a.bsearch { |x| 5 <=> x }   # => nil, 5 is absent

Band = Data.define(:name, :top, :bottom)
bands = [Band.new(:header, 0, 100), Band.new(:body, 100, 900), Band.new(:footer, 900, 1000)]

y = 450
bands.bsearch { |b| y < b.top ? -1 : (y >= b.bottom ? 1 : 0) }.name  # => :body

go deeper

for a junior

Recall that a numeric block switches bsearch to find-any mode and that 0 means a match.

for a middle

Explain the positive, zero, negative ordering and why the target goes on the left of <=>.

for a senior

Choose find-any for band or interval matching, and find-minimum when duplicates or first occurrences matter.

for a principal

Weigh the readability cost of three-way comparison blocks against the lookups they save in shared code.

## Selecting the mode `Array#bsearch`, `Array#bsearch_index` and `Range#bsearch` choose their mode from the block's return value on each probe: - `true`, `false` or `nil` means **find-minimum** mode. - A **number** means **find-any** mode. - Anything else raises `TypeError`. The block should not mix the two kinds of result; Ruby does not check, and mixed results give meaningless answers. ## What the number means In find-any mode the block tells the search which way to go from the probed element: | Block returns | Meaning | Search action | |---|---|---| | `0` | this element matches | return it | | positive | the target is to the right | discard the left half | | negative | the target is to the left | discard the right half | For that to work, the results over the sorted array must run **positive, then zero, then negative**. The Ruby documentation states the requirement the same way: every positive-evaluating element precedes every zero-evaluating one, which precede every negative-evaluating one. ## Why target <=> element On an ascending array `[0, 4, 7, 10, 12]` searching for 7: - `7 <=> x` gives `1, 1, 0, -1, -1`: positive, then zero, then negative. **Correct shape.** - `x <=> 7` gives `-1, -1, 0, 1, 1`: negative first. **Wrong shape.** With the reversed block, a probe that lands on a smaller element reports "go left", away from the target. On this array the search for 7 still succeeds by luck, because 7 is the first probe; a search for 4 with `x <=> 4` probes 7, gets `1`, moves right and returns `nil`. The rule of thumb is to put the **target on the left** of `<=>`. ## Some match, not the first Find-any mode stops at the first probe that returns `0`. With duplicates, which one that is depends on where the probes land: 1. On `[0, 100, 100, 100, 200]`, a find-any search for 100 may return the element at index 1, 2 or 3. 2. When you need the first occurrence, use find-minimum mode with `x >= target` instead. 3. When any match will do, find-any saves the separate equality check. ## Matching a band Find-any mode shines when a whole band of elements counts as a match, for example sorted, non-overlapping intervals: - The block returns `0` when the probed interval contains the target. - It returns positive when the target lies after the interval, and negative when before. - The search then finds the containing interval in O(log n). ## A drawing app example A drawing app splits a long canvas into horizontal bands, stored sorted by their top edge, and needs the band under the pointer's y coordinate: - Each band has `top` and `bottom`, and bands do not overlap. - `bands.bsearch { |b| y < b.top ? -1 : (y >= b.bottom ? 1 : 0) }` returns the band containing `y`, or `nil` if the pointer is off the canvas. - Returning `-1` when `y` is above the band steers the search left, and `1` when below steers it right, which is the target-relative sign convention again. ## When to prefer find-minimum Find-any mode is a niche tool. Most lookups on sorted arrays are clearer as find-minimum searches with `>=`, which have one correct answer and are easier to review. Reach for find-any when the comparison is naturally three-way and any match is acceptable.

  • On [0, 100, 100, 100, 200], which element does a find-any search for 100 return?
    Some element equal to 100, at index 1, 2 or 3 depending on where the probes land; the documentation promises only that it returns an element for which the block returns zero. For the first occurrence, use find-minimum mode with `x >= 100` or `bsearch_index` in that mode.
  • What happens if the block returns true on some probes and 1 on others?
    Ruby does not detect the mix. Each probe is interpreted by its own return value, so the search follows inconsistent rules and the result is meaningless. Keep a block to one mode.

saying these in an interview costs you the question

  • Any Comparable block like x <=> target works in find-any mode
  • Find-any mode always returns the first matching element
  • A numeric block result raises TypeError in bsearch
  • Returning 1 tells bsearch the element is too big
  • Find-any and find-minimum can be mixed in one block