sortedIndex with binary search

Write two functions that find where a value belongs in an array that's already sorted from smallest to largest. Each takes the sorted array and a value, and returns an index from 0 to array.length. Inserting value at that index keeps the array sorted.

sortedIndex(array, value) returns the lowest such index, which is before any items equal to value. sortedLastIndex(array, value) returns the highest, which is after any items equal to value.

The items and value are all numbers or all strings: compare them with < and >. Neither function changes array.

Both must take O(log n) steps, not O(n): for an array of 1,000 items, read at most 20 of its items. The tests count the reads.

sortedIndex([10, 20, 30, 40], 25);   // 2
sortedIndex([1, 2, 2, 2, 3], 2);     // 1
sortedLastIndex([1, 2, 2, 2, 3], 2); // 4
sortedIndex(["ant", "cat"], "bee");  // 1
sortedIndex([], 5);                  // 0
 
const scores = [10, 20, 30];
scores.splice(sortedIndex(scores, 25), 0, 25);
scores; // [10, 20, 25, 30]

What the tests check

1. 1finds where a value goes in a sorted array

   expect(sortedIndex([10, 20, 30, 40], 25)).toBe(2);
   expect(sortedLastIndex([10, 20, 30, 40], 25)).toBe(2);
   expect(sortedIndex([10, 20, 30, 40], 35)).toBe(3);
   

2. 2returns 0 for a value smaller than every item, or an empty array

   expect(sortedIndex([10, 20], 5)).toBe(0);
   expect(sortedLastIndex([10, 20], 5)).toBe(0);
   expect(sortedIndex([], 5)).toBe(0);
   expect(sortedLastIndex([], 5)).toBe(0);
   

3. 3returns the length for a value larger than every item

   expect(sortedIndex([10, 20], 25)).toBe(2);
   expect(sortedLastIndex([10, 20], 25)).toBe(2);
   expect(sortedLastIndex([10, 20], 20)).toBe(2);
   

4. 4sortedIndex goes before equal items

   expect(sortedIndex([1, 2, 2, 2, 3], 2)).toBe(1);
   expect(sortedIndex([5, 5, 5], 5)).toBe(0);
   expect(sortedIndex([1, 2, 2, 2, 3], 3)).toBe(4);
   

5. 5sortedLastIndex goes after equal items

   expect(sortedLastIndex([1, 2, 2, 2, 3], 2)).toBe(4);
   expect(sortedLastIndex([5, 5, 5], 5)).toBe(3);
   expect(sortedLastIndex([1, 2, 2, 2, 3], 1)).toBe(1);
   

6. 6works with strings

   expect(sortedIndex(["ant", "bee", "cat"], "bat")).toBe(1);
   expect(sortedLastIndex(["ant", "bee", "bee", "cat"], "bee")).toBe(3);
   

7. 7agrees with counting the smaller items, for many values

   const sorted = [0, 0, 2, 4, 4, 4, 6, 8, 10, 10, 11];
   for (let value = -1; value <= 12; value += 0.5) {
     expect(sortedIndex(sorted, value)).toBe(sorted.filter((item) => item < value).length);
     expect(sortedLastIndex(sorted, value)).toBe(sorted.filter((item) => item <= value).length);
   }
   

8. 8reads at most 20 items of a 1,000-item array

   const data = Array.from({ length: 1000 }, (_, i) => i * 2);
   let reads = 0;
   const watched = new Proxy(data, {
     get(target, key, receiver) {
       if (typeof key === "string" && /^\d+$/.test(key)) reads++;
       return Reflect.get(target, key, receiver);
     },
   });
   for (const value of [-5, 0, 777, 1000, 1998, 5000]) {
     reads = 0;
     const index = sortedIndex(watched, value);
     expect(reads).toBeLessThanOrEqual(20);
     expect(index).toBe(data.filter((item) => item < value).length);
     reads = 0;
     const lastIndex = sortedLastIndex(watched, value);
     expect(reads).toBeLessThanOrEqual(20);
     expect(lastIndex).toBe(data.filter((item) => item <= value).length);
   }
   

Learn more

• Searching arraysLesson
• Loops: while & forLesson