In Ruby, why does [0, 4, 7, 10, 12].bsearch { |x| x == 4 } return nil, and how should find-minimum mode be used?

middleshould knowfreq 30%

answer

block must be monotone: false... then true
== is not monotone
x >= target finds the first match
bsearch_index returns the position
nil when no element satisfies

basics

~20 s

Find-minimum mode needs a block that is false for a prefix and true for the rest; bsearch returns the first true element. x == 4 is true at one spot only, so the probes skip it; use x >= 4, then compare.

solid answer

~40 s

Array#bsearch with a block returning true/false runs in find-minimum mode: it assumes the array is sorted so that the block is false for every element before some point and true from there on, and it returns the first element where the block is true, in O(log n). x == 4 breaks that shape: the first probe is the middle element 7, the block says false, so the search moves right and never sees 4, returning nil. The idiom is x >= target, which returns the first element at or above the target; then check equality yourself. bsearch_index does the same but returns the index, which doubles as the insertion point for keeping an array sorted; nil means every element is smaller. Neither method checks that the array is sorted.

`Array#bsearch` with a block returning `true`/`false` runs in **find-minimum** mode: it assumes the array is sorted so that the block is `false` for every element before some point and `true` from there on, and it returns the **first** element where the block is `true`, in O(log n). `x == 4` breaks that shape: the first probe is the middle element 7, the block says `false`, so the search moves right and never sees 4, returning `nil`. The idiom is `x >= target`, which returns the first element at or above the target; then check equality yourself. `bsearch_index` does the same but returns the index, which doubles as the insertion point for keeping an array sorted; `nil` means every element is smaller. Neither method checks that the array is sorted.

code

ruby · 14 lines

ruby

a = [0, 4, 7, 10, 12]

a.bsearch { |x| x == 4 }        # => nil, not monotone
a.bsearch { |x| x >= 4 }        # => 4
a.bsearch { |x| x >= 6 }        # => 7, first element >= 6
a.bsearch { |x| x >= 100 }      # => nil

a.bsearch_index { |x| x >= 6 }  # => 2

# Insertion point for a stroke timestamp:
stamps = [100, 250, 400]
at = stamps.bsearch_index { |s| s >= 300 } || stamps.size  # => 2

a.bsearch { |x| x.to_s }        # TypeError: wrong argument type String (must be numeric, true, false or nil)

go deeper

for a junior

Recall that bsearch needs a sorted array, returns nil when nothing matches, and that bsearch_index returns a position.

for a middle

Explain the false-then-true requirement, trace why x == target fails, and use x >= target with an equality check.

for a senior

Spot unsorted inputs and non-monotone blocks in review, since both fail silently, and use bsearch_index for sorted inserts.

for a principal

Judge when a sorted array with bsearch beats a Hash or a database index for lookups over data that changes.

Two methods, one search

Ruby's core binary searches are block-driven:

Array#bsearch returns the element the search selects, or nil.
Array#bsearch_index returns that element's index, or nil.
Range#bsearch searches a range of numbers the same way, useful for searching over indexes or a numeric answer space.

Without a block each returns an Enumerator. With a block, the block's return values decide the mode. A block returning true, false or nil puts the search in find-minimum mode; nil counts as false.

The monotone requirement

Find-minimum mode needs the block to be monotone over the array: every element for which it returns false must come before every element for which it returns true.

Block on `[0, 4, 7, 10, 12]`	Values per element	Monotone?
`x >= 4`	false, true, true, true, true	yes
`x >= 6`	false, false, true, true, true	yes
`x >= 100`	all false	yes, result `nil`
`x == 4`	false, true, false, false, false	no

The search returns the first element where the block is true. Ruby does not check that the array is sorted or that the block is monotone; a violated assumption produces a wrong answer, not an error.

Tracing the == trap

With x == 4 on [0, 4, 7, 10, 12]:

The first probe is the middle element, 7. 7 == 4 is false, so the search concludes the answer lies to the right.
The next probe is 12, also false, so the search keeps moving right.
The range is exhausted without any true, so bsearch returns nil, although 4 is in the array.

x == 7 happens to work on this array only because 7 is the first probe, which is exactly why this bug survives quick tests.

The idioms

Lower bound: a.bsearch { |x| x >= target } returns the first element not smaller than the target.
Exact lookup: take that result and compare it: found = a.bsearch { |x| x >= target }; found if found == target.
Insertion point: a.bsearch_index { |x| x >= value } || a.size is the index where value goes to keep the array sorted.
Upper bound: x > target returns the first element strictly greater.

Wrong return types

The block must return true, false, nil or a number. Anything else raises TypeError with wrong argument type String (must be numeric, true, false or nil) for a String, for example. A number switches the search into the other mode, find-any, so returning an Integer by accident changes the semantics rather than raising.

A drawing app example

A drawing app records strokes with ascending timestamps in milliseconds. When the user scrubs the replay timeline to time t:

strokes.bsearch_index { |s| s.at >= t } finds the first stroke at or after t in O(log n).
nil means the scrubber is past the last stroke, so the replay shows the full drawing.
Inserting a late-arriving stroke uses the same call to find its slot, keeping the array sorted without a full sort after each insert.

The array must actually be sorted by at; if strokes can arrive out of order and are appended blindly, bsearch_index quietly returns wrong positions.

## Two methods, one search Ruby's core binary searches are block-driven: - **`Array#bsearch`** returns the **element** the search selects, or `nil`. - **`Array#bsearch_index`** returns that element's **index**, or `nil`. - **`Range#bsearch`** searches a range of numbers the same way, useful for searching over indexes or a numeric answer space. Without a block each returns an Enumerator. With a block, the block's return values decide the mode. A block returning `true`, `false` or `nil` puts the search in **find-minimum mode**; `nil` counts as `false`. ## The monotone requirement Find-minimum mode needs the block to be **monotone** over the array: every element for which it returns `false` must come before every element for which it returns `true`. | Block on `[0, 4, 7, 10, 12]` | Values per element | Monotone? | |---|---|---| | `x >= 4` | false, true, true, true, true | yes | | `x >= 6` | false, false, true, true, true | yes | | `x >= 100` | all false | yes, result `nil` | | `x == 4` | false, true, false, false, false | **no** | The search returns the first element where the block is `true`. Ruby does **not** check that the array is sorted or that the block is monotone; a violated assumption produces a wrong answer, not an error. ## Tracing the == trap With `x == 4` on `[0, 4, 7, 10, 12]`: 1. The first probe is the middle element, **7**. `7 == 4` is `false`, so the search concludes the answer lies to the right. 2. The next probe is **12**, also `false`, so the search keeps moving right. 3. The range is exhausted without any `true`, so `bsearch` returns **`nil`**, although 4 is in the array. `x == 7` happens to work on this array only because 7 is the first probe, which is exactly why this bug survives quick tests. ## The idioms - **Lower bound:** `a.bsearch { |x| x >= target }` returns the first element not smaller than the target. - **Exact lookup:** take that result and compare it: `found = a.bsearch { |x| x >= target }; found if found == target`. - **Insertion point:** `a.bsearch_index { |x| x >= value } || a.size` is the index where `value` goes to keep the array sorted. - **Upper bound:** `x > target` returns the first element strictly greater. ## Wrong return types The block must return `true`, `false`, `nil` or a number. Anything else raises `TypeError` with `wrong argument type String (must be numeric, true, false or nil)` for a String, for example. A **number** switches the search into the other mode, find-any, so returning an Integer by accident changes the semantics rather than raising. ## A drawing app example A drawing app records strokes with ascending timestamps in milliseconds. When the user scrubs the replay timeline to time `t`: - `strokes.bsearch_index { |s| s.at >= t }` finds the first stroke at or after `t` in O(log n). - `nil` means the scrubber is past the last stroke, so the replay shows the full drawing. - Inserting a late-arriving stroke uses the same call to find its slot, keeping the array sorted without a full `sort` after each insert. The array must actually be sorted by `at`; if strokes can arrive out of order and are appended blindly, `bsearch_index` quietly returns wrong positions.

What happens if you call bsearch on an unsorted array?
Ruby does not check. The search still makes O(log n) probes and returns whatever its comparisons lead to, which can be `nil` for a present element or an element that is not the first match. Sort the array, or keep it sorted on insert, before relying on `bsearch`.
How do you find the index where a new value should be inserted to keep an array sorted?
Use `a.bsearch_index { |x| x >= value } || a.size`. The block finds the first element not smaller than `value`; `nil` means every element is smaller, so the value belongs at the end.

saying these in an interview costs you the question

bsearch { |x| x == target } is the normal exact lookup
bsearch sorts the array before searching
bsearch raises an error when the array is unsorted
bsearch returns the index of the match
A nil block result raises TypeError

In Ruby, why does [0, 4, 7, 10, 12].bsearch { |x| x == 4 } return nil, and how should find-minimum mode be used?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~3 min

Two methods, one search

The monotone requirement

Tracing the == trap

The idioms

Wrong return types

A drawing app example

▾common follow-ups2 questions

▾red flags5 flags

Two methods, one search

The monotone requirement

Tracing the == trap

The idioms

Wrong return types

A drawing app example

answer

go deeper