binary-search-maa

Binary Search

A function that takes in a sorted array (arr), an item to search (srch) and optionally a compare function (compareFunction) used to compare elements in array

The compare function takes two arguments a and b and should return a number < 0 if a < b, 0 if a = b, and a number > 0 if a > b)

The search returns an object ({found: boolean, index: number}) with 'found' property to indicate if srch was found in arr, and an 'index' property indicating the first occurence of srch if it was found or the index to insert srch in so as array is still sorted (might be arr.length if srch is greater than all items in array)

import binarySearch from 'binary-search';

const { found, index } = binarySearch([0, 1, 2, 4], 1);
// found = true, index = 1

const { found, index } = binarySearch([0, 1, 2, 4], 3);
// found = false, index = 3

const { found, index } = binarySearch([0, 1, 2, 4], 4);
// found = true, index = 3

const { found, index } = binarySearch([0, 1, 1, 1, 1, 1, 2, 4], 1);
// found = true, index = 1(always)

// demo usage to insert srch in arr in the correct position if it does not exists
const { found, index } = binarySearch(arr, srch);
if(!found) {
  arr.splice(index, 0, srch);
}

// can send a comparison function, e.g. sorted desc:
const { found, index } = binarySearch([4, 2, 1, 0], 1, (a, b) => b - a);
// found = true, index = 2