Lodash sortedLastIndexOf with Sparse Arrays

This article explores how Lodash’s _.sortedLastIndexOf function interacts with sparse arrays containing missing indices or empty slots. Because _.sortedLastIndexOf relies on a binary search algorithm designed for contiguous, sorted data, encountering empty indices causes JavaScript to evaluate missing elements as undefined. This disrupts the search logic, leading to inaccurate index calculations or unexpected -1 return values.

Mechanism of _.sortedLastIndexOf

The _.sortedLastIndexOf method performs a binary search over an array that is assumed to be sorted in ascending order. Instead of iterating sequentially from the end of the collection like _.lastIndexOf, it repeatedly divides the search range in half to find the highest index at which a specified value appears.

For the binary search to function correctly, the dataset must satisfy a strict sorting invariant where every element at index i is less than or equal to the element at index i + 1.

How Sparse Arrays Interfere with the Search

A sparse array in JavaScript contains "holes"—indices that have not been assigned a value (for example, [1, , , 4]). When Lodash retrieves an element at a midpoint index using bracket notation (array[mid]), accessing an empty slot evaluates to undefined.

This creates two critical issues for _.sortedLastIndexOf:

1. Broken Relational Comparisons: In JavaScript, relational comparisons involving undefined (such as value < undefined or undefined < value) evaluate to false. The binary search algorithm uses these comparisons to determine whether to branch left or right. When comparisons fail silently, the search boundary moves in the wrong direction.
2. Violation of Sorted Order: Even if all defined numbers in a sparse array appear in ascending order, the implicit undefined values scattered throughout the array violate the monotonic order required by binary search algorithms.

Resulting Behavior

When calling _.sortedLastIndexOf on a sparse array:

• Missed Matches: If a midpoint lands on an unassigned index, the search algorithm miscalculates the search window and often fails to locate a value that actually exists in the array, returning -1.
• Incorrect Indices: If the algorithm terminates prematurely or converges on an incorrect offset due to failed comparison branches, it will return -1 because the final equality check against the target value fails.
• Searching for undefined: If you explicitly search for undefined using _.sortedLastIndexOf, the method will still not reliably locate missing slots because the binary search logic does not treat sparse holes as an ordered set of elements unless they are packed contiguously at the end of the array.

Example

const _ = require('lodash');

// A sparse array with holes at indices 1 and 2
const sparseArray = [10, , , 20, 20, 30];

// Expected to find the last index of 20 (index 4)
console.log(_.sortedLastIndexOf(sparseArray, 20)); // May output -1 or an incorrect index

In this scenario, if the binary search checks index 2 (an empty slot evaluating to undefined), the relational comparison fails, causing the algorithm to discard the partition containing the target value.

Recommended Solution

To safely use _.sortedLastIndexOf, normalize sparse arrays into dense arrays prior to execution. Removing missing slots or re-indexing guarantees that the binary search operates across continuous, predictable boundaries:

• Use Array.prototype.filter() or Lodash’s _.compact() to eliminate holes if falsy values are not needed.
• Use Array.from(sparseArray) to convert holes into explicit undefined values, then sort the array so that all undefined values are shifted to the end, preserving the sorting contract required by the method.