Natural Pacifist Manatees

    bsearch
    TypeScript icon, indicating that this package has built-in type declarations

    1.0.0 • Public • Published

    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
    })

    Install

    npm i bsearch

    DownloadsWeekly Downloads

    21

    Version

    1.0.0

    License

    MIT

    Unpacked Size

    204 kB

    Total Files

    19

    Last publish

    Collaborators

    • dtinth
    • dtinth-bot