Binary search over a sorted list
Sorted data turns up constantly on the client: a timeline of messages by timestamp, a price ladder, a list of sorted option values in a combobox. Scanning it linearly wastes the fact that it is sorted.
Implement binarySearch(sorted, target). sorted is an array of numbers in ascending order with no duplicate values, and target is a number. Return the index of target in the array, or -1 when the array does not contain it. An empty array always returns -1.
Arguments
sortednumber[]- An array of numbers already in ascending order with no duplicates.
targetnumber- The value to locate.
Returns
number — The index of target in sorted, or -1 when it is not present.
Examples
binarySearch([1, 3, 5, 7, 9, 11], 7);
// 3A straight hit in the middle of the array.
binarySearch([1, 3, 5, 7, 9, 11], 4);
// -1No match returns -1 rather than the nearest neighbour.
binarySearch([], 42);
// -1An empty array always returns -1.
What it has to do
- Return the index of the target when it is present.
- Return
-1when the target is absent. - Return
-1for an empty array. - Halve the search range each step rather than scanning every element.
Notes
- Binary search runs in O(log n) time and O(1) space — the whole appeal over
indexOf. - The classic bug is computing
(low + high) / 2without flooring: useMath.floorso the index stays an integer. - If you ever need the position for an *absent* value too, reach for the insertion-position variant instead of patching this one.
Stuck? The javascript course covers everything this challenge needs.
- 1.finds a value in the middle
- 2.finds the first and last values
- 3.returns -1 when the value is absent
- 4.handles empty and single element arrays
- 5.works with negative numbers
These assertions run in your browser the moment you hit Run. Pass all of them to claim the XP.
Discussion
Sign in to postNo comments yet. Be the first to say something.