binary-search-algorithms

Набор функций двоичного поиска индекса элемента в отсортированных срезах данных.

Установка

NPM:

npm install binary-search-algorithms

Использование

Библиотека предоставляется в виде ECMAScript модуля. Пример использования:

import { findFirst } from 'binary-search-algorithms/sync'
const array = [ 11, 11, 22, 33, 44, 55, 55, 66, 66, 66, 77, 88, 99 ]
    // индексы:  0   1   2   3   4   5   6   7   8   9  10  11  12
const first = 0, last = array.length - 1
const key = 66
console.log(findFirst(i => array[i] - key, first, last)) // 7

Описание API

Библиотека предоставляет следующие асинхронные функции (импортируются из binary-search-algorithms/async):

• findFirst(compareWith, low, high) - найти в срезе данных индекс первого элемента, значение которого совпадает с искомым, возвращает целочисленный индекс в случае успеха, иначе -1
• findLast(compareWith, low, high) - найти в срезе данных индекс последнего значения, значение которого совпадает с искомым, возвращает целочисленный индекс в случае успеха, иначе -1
• findGreater(compareWith, low, high) - найти в срезе данных индекс первого элемента, значение которого больше чем искомое, возвращает целочисленный индекс в случае успеха, иначе -1
• findGreaterOrEqual(compareWith, low, high) - найти в срезе данных индекс первого элемента, значение которого больше либо равно искомому, возвращает целочисленный индекс в случае успеха, иначе -1
• findLess(compareWith, low, high) - найти в срезе данных индекс последнего элемента, значение которого меньше чем искомое, возвращает целочисленный индекс в случае успеха, иначе -1
• findLessOrEqual(compareWith, low, high) - найти в срезе данных индекс последнего элемента, значение которого меньше либо равно искомому, возвращает целочисленный индекс в случае успеха, иначе -1
• isContains(compareWith, low, high) - проверить входит ли в срез данных искомое значение, возвращает логическое значение true - если элемент входит в массив, иначе - false

А также синхронные версии этих функций (импортируются из binary-search-algorithms/sync):

• findFirst(compareWithSync, low, high)
• findLast(compareWithSync, low, high)
• findGreater(compareWithSync, low, high)
• findGreaterOrEqual(compareWithSync, low, high)
• findLess(compareWithSync, low, high)
• findLessOrEqual(compareWithSync, low, high)
• isContains(compareWithSync, low, high)

Все функции из данной библиотеки принимают на вход следующие параметры:

• compareWith(i) или compareWithSync(i) - асинхронный или синхронный вариант функции оценки движения поиска. В типичных случаях это замыкание для сравнения значения элемента под индексом i со значением искомого элемента, причем само значение искомого элемента заключено в область видимости замыкания. Логика извлечения и сравнения данных возлагается на это замыкание, что позволяет, например, использовать удаленные API вызовы. Возвращает:
  • 0, если значение элемента под индексом i равно значению искомого элемента;
  • <0, если значение элемента под индексом i меньше значения искомого элемента;
  • >0, если значение элемента под индексом i больше значения искомого элемента;
• low - нижняя граница рассматриваемого среза данных (включительно)
• high - верхняя граница рассматриваемого среза данных (включительно)