bsearch

bsearch

Utility functions for performing binary search in various scenarios (sync/async, ints/arrays/floats).

Available functions

Use case	Sync	Async
Integers	smallestInt largestInt	smallestIntAsync largestIntAsync
Floats	smallestFloat largestFloat	smallestFloatAsync largestFloatAsync
Array indices	firstIndex lastIndex	firstIndexAsync lastIndexAsync
Array elements	firstElement lastElement	firstElementAsync lastElementAsync

API reference

https://apiref.page/package/bsearch

Example: Looking up chapter from page number

Suppose you have an array of chapters in a book.

const book = [
  { page: 0, chapter: 'Front Cover' },
  { page: 2, chapter: 'Preamble' },
  { page: 5, chapter: 'Table of Contents' },
  { page: 8, chapter: 'Chapter 1' },
  { page: 29, chapter: 'Chapter 2' },
  { page: 48, chapter: 'Chapter 3' },
]

To answer the question: “What chapter am I on if I’m on page 20?”

• Translate the question into “What is the last chapter I have started?”
• Define “I have started” as “I’m on or after the chapter’s first page.”

With that, the following code finds the answer:

import * as bsearch from 'bsearch'
const chapter = bsearch.lastElement(book, (chapter) => 20 >= chapter.page)

Example: Insertion index

Suppose you have an array of numbers.

const numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

You want to insert a new number n into the array while maintaining the sorted order. There are two ways:

• Finding the first possible insertion index:

  const indexToInsertBefore = bsearch.firstIndex(numbers, (x) => n <= x)
  const insertionIndex =
    indexToInsertBefore === -1 ? numbers.length : indexToInsertBefore
  

• Finding the last possible insertion index:

  const indexToInsertAfter = bsearch.lastIndex(numbers, (x) => n >= x)
  const insertionIndex = indexToInsertBefore + 1
  

Example: Text fitting

Suppose you want to draw some text in a canvas. You want to find out what is the largest possible font size that will fit the text within a given width.

const fontSize = bsearch.largestInt(1, 1000, (fontSize) => {
  ctx.font = `${fontSize}px sans-serif`
  return ctx.measureText(text).width <= availableWidth
})