Ruby's Array.bsearch in TypeScript

How to use

Install via yarn add locutus and import: import { bsearch } from 'locutus/ruby/Array/bsearch'.

Or with CommonJS: const { bsearch } = require('locutus/ruby/Array/bsearch')

Use a bundler that supports tree-shaking so you only ship the functions you actually use. Vite, webpack, Rollup, and Parcel all handle this. For server-side use this is less of a concern.

Examples

These examples are extracted from test cases that automatically verify our functions against their native counterparts.

#	code	expected result
1	bsearch([1, 3, 4, 6, 8], (value) => value >= 4)	4
2	bsearch([1, 3, 4, 6, 8], (value) => (value === 4 ? 0 : 4 > value ? 1 : -1))	4
3	bsearch([1, 3, 4, 6, 8], (value) => (value === 5 ? 0 : 5 > value ? 1 : -1))	null

Ruby nil and TypeScript/JavaScript undefined

Ruby's nil and TypeScript/JavaScript undefined are semantically equivalent—both represent "no value" or "nothing here". However, they serialize differently: nil becomes null in JSON, while undefined is typically omitted or becomes undefined.

Locutus Ruby functions return undefined (idiomatic TypeScript/JavaScript) where Ruby would return nil. Our parity tests treat these as equivalent when verifying against native Ruby.

Notes

• Supports Ruby’s boolean “find minimum” mode and numeric “find any exact match” mode.

• In numeric mode, positive means search right, negative means search left, and zero means match.

Here's what our current TypeScript equivalent to Ruby's Array.bsearch looks like.

TSTypeScript JSJavaScript TSStandalone TS JSStandalone JS

Copy code

type BsearchCallback<T> = (value: T, index: number, array: T[]) => boolean | number | null | undefined

export function bsearch<T>(values: T[] | unknown, callback: BsearchCallback<T>): T | null {
  //      discuss at: https://locutus.io/ruby/Array/bsearch/
  // parity verified: Ruby 3.3
  //     original by: Kevin van Zonneveld (https://kvz.io)
  //          note 1: Supports Ruby's boolean "find minimum" mode and numeric "find any exact match" mode.
  //          note 2: In numeric mode, positive means search right, negative means search left, and zero means match.
  //       example 1: bsearch([1, 3, 4, 6, 8], (value) => value >= 4)
  //       returns 1: 4
  //       example 2: bsearch([1, 3, 4, 6, 8], (value) => (value === 4 ? 0 : 4 > value ? 1 : -1))
  //       returns 2: 4
  //       example 3: bsearch([1, 3, 4, 6, 8], (value) => (value === 5 ? 0 : 5 > value ? 1 : -1))
  //       returns 3: null

  if (typeof callback !== 'function') {
    throw new TypeError('bsearch(): callback must be a function')
  }

  if (!Array.isArray(values) || values.length === 0) {
    return null
  }

  let low = 0
  let high = values.length - 1
  let candidateIndex: number | null = null
  let mode: 'boolean' | 'numeric' | null = null

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2)
    const value = values[mid] as T
    const result = callback(value, mid, values)

    if (typeof result === 'number') {
      if (mode === 'boolean') {
        throw new TypeError('bsearch(): callback must consistently return booleans or numbers')
      }

      mode = 'numeric'

      if (result === 0) {
        return value
      }

      if (result > 0) {
        low = mid + 1
      } else {
        high = mid - 1
      }

      continue
    }

    if (mode === 'numeric') {
      throw new TypeError('bsearch(): callback must consistently return booleans or numbers')
    }

    mode = 'boolean'

    if (result) {
      candidateIndex = mid
      high = mid - 1
    } else {
      low = mid + 1
    }
  }

  return candidateIndex === null ? null : (values[candidateIndex] as T)
}

export function bsearch(values, callback) {
  //      discuss at: https://locutus.io/ruby/Array/bsearch/
  // parity verified: Ruby 3.3
  //     original by: Kevin van Zonneveld (https://kvz.io)
  //          note 1: Supports Ruby's boolean "find minimum" mode and numeric "find any exact match" mode.
  //          note 2: In numeric mode, positive means search right, negative means search left, and zero means match.
  //       example 1: bsearch([1, 3, 4, 6, 8], (value) => value >= 4)
  //       returns 1: 4
  //       example 2: bsearch([1, 3, 4, 6, 8], (value) => (value === 4 ? 0 : 4 > value ? 1 : -1))
  //       returns 2: 4
  //       example 3: bsearch([1, 3, 4, 6, 8], (value) => (value === 5 ? 0 : 5 > value ? 1 : -1))
  //       returns 3: null

  if (typeof callback !== 'function') {
    throw new TypeError('bsearch(): callback must be a function')
  }

  if (!Array.isArray(values) || values.length === 0) {
    return null
  }

  let low = 0
  let high = values.length - 1
  let candidateIndex = null
  let mode = null

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2)
    const value = values[mid]
    const result = callback(value, mid, values)

    if (typeof result === 'number') {
      if (mode === 'boolean') {
        throw new TypeError('bsearch(): callback must consistently return booleans or numbers')
      }

      mode = 'numeric'

      if (result === 0) {
        return value
      }

      if (result > 0) {
        low = mid + 1
      } else {
        high = mid - 1
      }

      continue
    }

    if (mode === 'numeric') {
      throw new TypeError('bsearch(): callback must consistently return booleans or numbers')
    }

    mode = 'boolean'

    if (result) {
      candidateIndex = mid
      high = mid - 1
    } else {
      low = mid + 1
    }
  }

  return candidateIndex === null ? null : values[candidateIndex]
}

Improve this function

Locutus is a community effort following The McDonald's Theory: we ship first iterations, hoping others will improve them. If you see something that could be better, we'd love your contribution.

View on GitHub · Edit on GitHub · View Raw

---

We have 40 Ruby functions so far - help us add more

Got a rainy Sunday afternoon and a taste for a porting puzzle?

• Get inspiration from the Ruby core documentation.
• Click "New file" in the appropriate folder on GitHub. This will fork the project to your account, directly add the file to it, and send a Pull Request to us.

We will then review it. If it's useful to the project and in line with our contributing guidelines your work will become part of Locutus and you'll be automatically credited in the authors section accordingly.

« More Ruby Array functions

Star