A typescript implementation of the upper bound algorithm.

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

Install

• npm

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

• yarn

  yarn add @algorithm.ts/upper-bound

• deno

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

Usage

• Basic

  import upperBound from '@algorithm.ts/upper-bound'
  
  // elements should be ordered.
  const elements: number[] = [2, 3, 7, 11, 19]
    
  // Find the index of elements which is the first element greater than 8
  // elements[3] = 11 >= 8
  upperBound(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] = 7 >= 3
  upperBound(0, elements.length, x => elements[x] - 3) // => 2

• Complex

  import upperBound from '@algorithm.ts/upper-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 9
  upperBound(0, fruits.length, x => fruits[x].price - 9) // => 1
  
  // Find the index of fruits which price is greater or equal than 10
  upperBound(0, fruits.length, x => fruits[x].price - 10) // => 3
  
  // Find the index of fruits which price is greater or equal than 11
  upperBound(0, fruits.length, x => fruits[x].price - 11) // => 3

• Bigint

  import { upperBoundBigint } from '@algorithm.ts/upper-bound'
  
  upperBoundBigInt(-500000000000n, 5000000000n, x => x - 1n) // => 2n

Related