A typescript implementation of the lower bound algorithm.

The lower bound algorithm is desired to find the index of first elements which greater or equals than the target element.

Install

• npm

  npm install --save @algorithm.ts/lower-bound

• yarn

  yarn add @algorithm.ts/lower-bound

• deno

  import lowerBound from 'https://raw.githubusercontent.com/guanghechen/algorithm.ts/main/packages/lower-bound/src/index.ts'

Usage

• Basic

  import lowerBound from '@algorithm.ts/lower-bound'
  
  // elements should be ordered.
  const elements: number[] = [2, 3, 7, 11, 19]
    
  // Find the index of elements which is the first element greater or equal than 8
  // elements[3] = 11 >= 8
  lowerBound(0, elements.length, x => elements[x] - 8) // => 3
  
  // Find the index of elements which is the first element greater or equal than 3
  // elements[1] = 3 >= 3
  lowerBound(0, elements.length, x => elements[x] - 3) // => 1

• Complex

  import lowerBound from '@algorithm.ts/lower-bound'
  
  const fruits = [
    { type: 'orange', price: 3 },
    { type: 'apple', price: 10 },
    { type: 'banana', price: 10 },
    { type: 'watermelon', price: 12 },
    { type: 'lemon', price: 15 },
  ]
  
  // Find the index of fruits which price is greater or equal than 10
  lowerBound(0, fruits.length, x => fruits[x].price - 10) // => 1
  
  // Find the index of fruits which price is greater or equal than 11
  lowerBound(0, fruits.length, x => fruits[x].price - 11) // => 3

• Bigint

  import { lowerBoundBigint } from '@algorithm.ts/lower-bound'
  
  lowerBoundBigint(-500000000000n, 5000000000n, x => x - 1n) // => 1n

Related