Binary search returning index or negative insertion point
A video player keeps a sorted list of caption cue start times. When the user scrubs to a time, the player needs to know two things fast: is there a cue that starts exactly here, and if not, where would a new cue go to keep the list sorted? The list can hold hundreds of thousands of cues, so scanning it is not an option.
Implement searchSorted(array, target, compare). It uses binary search to find target in a sorted array. Like Java’s Arrays.binarySearch, one number answers both questions.
searchSorted(array, target, compare?) // => number
target exists, return its index. With duplicates, return the first (smallest) such index.-(insertionPoint + 1), where insertionPoint is the index where target would be inserted to keep the array sorted (the index of the first element greater than target, or array.length if there is none).>= 0 means “found”, and a negative result r means “not found, insert at -r - 1“. The + 1 keeps “insert at 0” distinguishable from “found at 0”: it becomes -1. An empty array returns -1.compare(element, target) returns a negative number if element sorts before target, 0 if they are equal, and a positive number if it sorts after. Always call it in that argument order: an element of the array first, then target. This lets target be a different type, such as a key.compare is omitted, use (a, b) => (a < b ? -1 : a > b ? 1 : 0), which works for numbers and strings.compare.compare at most Math.ceil(Math.log2(array.length + 1)) + 1 times: 11 calls for 1,000 elements, 21 for a million, and none for an empty array. (The tests count calls when they pass a comparator.)const cues = [0, 4.5, 9, 9, 9, 15, 21];
searchSorted(cues, 15); // => 5
searchSorted(cues, 9); // => 2 first of the three 9s
searchSorted(cues, 10); // => -6 insert at 5
searchSorted(cues, -2); // => -1 insert at 0
searchSorted(cues, 30); // => -8 insert at 7 (the end)
searchSorted([], 3); // => -1
const chapters = [{ at: 0, title: 'Intro' }, { at: 95, title: 'Setup' }, { at: 300, title: 'Demo' }];
searchSorted(chapters, 95, (chapter, time) => chapter.at - time); // => 1
searchSorted(chapters, 120, (chapter, time) => chapter.at - time); // => -3
searchSorted(['kiwi', 'fig', 'date'], 'fig', (a, b) => (a > b ? -1 : a < b ? 1 : 0)); // => 1 (descending)