sortedIndexOf

arrays

This method is like indexOf except that it performs a binary search on a sorted array.

Installation

Import

import { sortedIndexOf } from '@tulx/utils';

Source Code

Implementation

/**
 * This method is like indexOf except that it performs a binary search on a sorted array.
 *
 * @param array - The array to inspect.
 * @param value - The value to search for.
 * @returns The index of the matched value, else -1.
 *
 * @example
 * ```ts
 * sortedIndexOf([4, 5, 5, 5, 6], 5); // 1
 * ```
 */
export function sortedIndexOf<T>(array: readonly T[], value: T): number {
  let low = 0;
  let high = array.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (array[mid] < value) {
      low = mid + 1;
    } else if (array[mid] > value) {
      high = mid - 1;
    } else {
      // Found value, but need to find first occurrence
      let firstIndex = mid;
      while (firstIndex > 0 && array[firstIndex - 1] === value) {
        firstIndex--;
      }
      return firstIndex;
    }
  }

  return -1;
}

Example

import { sortedIndexOf } from '@tulx/utils';

sortedIndexOf([4, 5, 5, 5, 6], 5); // 1

Related Functions

chunk

Creates an array of elements split into groups the length of size. If array can't be split evenly, the final chunk will be the remaining elements.

compact

Creates an array with all falsy values removed. The values false, null, 0, "", undefined, and NaN are falsy.

concat

Creates a new array concatenating array with any additional arrays and/or values.

difference

Creates an array of array values not included in the other given arrays. The order and references of result values are determined by the first array.

differenceBy

This method is like difference except that it accepts iteratee which is invoked for each element of array and values to generate the criterion by which they're compared.

differenceWith

This method is like difference except that it accepts comparator which is invoked to compare elements of array to values.