@algorithm.ts/binary-search
v4.0.0
Published
Find the index of first elements which greater or equals than the target element.
Downloads
44
Readme
Typescript implementations of the binary search related algorithm. Different from the traditional implementation which find the element in an array with the given condition, this implementation aims to find a number that satisfied the target condition in the given interval. The condition checker receive the number currently found as parameter and returns a number indicating the difference between the currently checking number and the target number. When the returned value is
< 0
: It means that the target number is on the right side of the currently checking number.= 0
: It means that this currently checking number is a target number but it does not guarantee that there are no other numbers that meet the conditions.> 0
: It means that the target number is on the left side of the currently checking number.
This package contains three binary search related algorithm implemented in Typescript:
binary-search (integer / bigint): Find a number in the given interval such that it satisfies the given condition.
- If there is no such a number, return
null
. - if there are multiple such numbers, return any one of them.
- If there is no such a number, return
lower-bound (integer / bigint): Find the smallest number in the given interval such that it satisfies the given condition.
- If there is no such a number, return the first number that greater than the target number.
upper-bound (integer / bigint): Find the smallest number in the given interval such that it is greater than the target number.
- If there is no such a number, return the right boundary of the given interval + 1.
Install
npm
npm install --save @algorithm.ts/binary-search
yarn
yarn add @algorithm.ts/binary-search
Usage
Basic
import { binarySearch, lowerBound, upperBound } from '@algorithm.ts/binary-search' // elements should be ordered. const elements: number[] = [2, 3, 7, 11, 19] // Find the first index of elements which are greater or equal than 8 // elements[3] = 11 >= 8 lowerBound(0, elements.length, x => elements[x] - 8) // => 3 // Find the first index of elements which are greater than 8 // elements[3] = 11 > 8 upperBound(0, elements.length, x => elements[x] - 8) // => 3 // Find the first index of elements which are equal than 8 // No such an element equals with 8. binarySearch(0, elements.length, x => elements[x] - 8) // => null // Find the first index of elements which are greater or equal than 3 // elements[1] = 3 >= 3 lowerBound(0, elements.length, x => elements[x] - 3) // => 1 // Find the first index of elements which are greater than 3 // elements[2] = 7 > 3 upperBound(0, elements.length, x => elements[x] - 3) // => 7 // Find the first index of elements which are equal than 3 // No such an element equals with 8. binarySearch(0, elements.length, x => elements[x] - 3) // => 1
Advance
import { lowerBound ] from '@algorithm.ts/binary-search' 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/binary-search' lowerBoundBigint(-500000000000n, 5000000000n, x => x - 1n) // => 1n