Lodash sortedIndexOf with Duplicate Values

In the Lodash JavaScript library, _.sortedIndexOf uses a binary search algorithm to locate a value within a sorted array. When applied to an array containing highly duplicated matching values, _.sortedIndexOf is guaranteed to return the lowest (first) index at which the target value appears. It achieves this with logarithmic time complexity, ensuring predictable and fast lookups regardless of how many identical elements exist.

The Mechanism Behind Duplicate Resolution

Under the hood, _.sortedIndexOf delegates its search logic to Lodash's _.sortedIndex. The _.sortedIndex function performs a modified binary search designed to find the earliest insertion position for a value while preserving the array's ascending order.

When the binary search encounters duplicate target elements, it shifts its search bounds toward the left (lower indices). Once the lowest insertion index is determined, _.sortedIndexOf verifies whether the element at that index strictly equals the search target. If it matches, that index is returned; if not, -1 is returned.

Example Behavior

Consider an array where the search value appears repeatedly:

const _ = require('lodash');

const numbers = [10, 20, 30, 30, 30, 30, 30, 40, 50];

// Finds the first occurrence of 30
const firstIndex = _.sortedIndexOf(numbers, 30);
console.log(firstIndex); // Output: 2

Even if the array contained millions of matching values, the returned index would still be 2.

Performance with Massive Duplication

Because _.sortedIndexOf uses a binary search rather than a linear scan, its performance remains \(O(\log n)\) even in worst-case duplicate scenarios (such as an array composed entirely of the target value). It does not degrade to an \(O(n)\) scan to locate the boundaries of the duplicate sequence.

Finding the Opposite Boundary

If the desired outcome is to retrieve the highest (last) index of a duplicated sequence, Lodash provides a companion method: _.sortedLastIndexOf.

// Finds the last occurrence of 30
const lastIndex = _.sortedLastIndexOf(numbers, 30);
console.log(lastIndex); // Output: 6

While _.sortedLastIndexOf biases its search bounds to the right to capture the highest index, _.sortedIndexOf strictly confines its result to the very first matching index in the sorted collection.