Lodash sortedIndex with Unsorted Arrays

In the Lodash JavaScript library, _.sortedIndex uses a binary search algorithm to determine the lowest index at which a value should be inserted to maintain sorted order. When evaluated against an array that is completely unsorted, _.sortedIndex does not throw an error, but it returns an unpredictable and logically incorrect index. This article explains how the function behaves under the hood, demonstrates the resulting behavior with code, and outlines how to handle unsorted collections correctly.

How _.sortedIndex Operates

The _.sortedIndex method is strictly designed for sorted arrays. To maintain high performance (\(O(\log n)\) time complexity), it employs binary search:

1. It examines the middle element of the array.
2. It compares the target value to this midpoint.
3. It eliminates the half of the array where the value cannot logically reside, assuming elements ascend from lowest to highest.
4. It repeats this division until it isolates the target insertion point.

Because it relies on this divide-and-conquer logic, it depends entirely on the invariant that every element to the left of any index is smaller than or equal to the elements to the right.

The Behavior on an Unsorted Array

When an array is completely unsorted, the core invariant of binary search is broken. The function does not validate whether the array is sorted before running, as doing so would require an \(O(n)\) check that defeats the performance benefits of a binary search.

As a result, _.sortedIndex will:

• Execute without runtime errors: It will not crash or throw exceptions.
• Make flawed branch decisions: It will compare the target to whatever random values happen to sit at the midpoints.
• Discard valid insertion regions: Halves of the array containing the actual optimal positions will be skipped entirely.
• Return an arbitrary index: The returned number will be a valid index within the bounds of the array (between 0 and array.length), but inserting the item at that position will not produce a sorted array.

Example

Consider this scenario using an unsorted array:

const _ = require('lodash');

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

// Attempting to find the index for 25
const index = _.sortedIndex(unsortedArray, 25);

console.log(index); 
// Output might be 2 or another arbitrary index, depending on midpoint evaluations.

// Inserting 25 at the returned index:
unsortedArray.splice(index, 0, 25);
console.log(unsortedArray);
// Output: [50, 10, 25, 40, 20, 30] -> Array remains unsorted.

In this example, placing 25 at index 2 fails to achieve any sorted order. The output index is merely the artifact of binary search decisions made on disordered data.

Correct Alternatives

If the array is not guaranteed to be sorted, choose an alternative approach based on the desired outcome:

1. Sort the array first: If future operations require binary search performance, sort the array prior to calling _.sortedIndex.

   const sorted = _.sortBy(unsortedArray);
   const index = _.sortedIndex(sorted, 25);

2. Linear search for insertion: If sorting the entire array is undesirable and you merely need to insert an element into an ad-hoc position, find the index using standard linear search (Array.prototype.findIndex) or insert and sort afterward:

   unsortedArray.push(25);
   unsortedArray.sort((a, b) => a - b);