ScriptdrillBinary search
A JavaScript exercise from Scriptdrill. Solve it with a code editor in your browser that runs your function against example and hidden tests, and it is checked the moment you submit.
The task
`sorted` is an array of numbers in ascending order with no duplicates. Return the index of `target`, or `-1` when it is not there. Use binary search: keep a low and a high index and halve the range on every step. One hidden test counts how many elements you read from an array of one million numbers and allows at most 40 reads, so scanning from the start (or `indexOf`) fails it.
What this exercise teaches
Each step discards half of the remaining range, so a million elements take at most 20 reads. The loop condition must be lo <= hi: with lo < hi a range of one element is never checked, which breaks single-element arrays and the last element.
A hint if you get stuck
Start with `lo = 0` and `hi = sorted.length - 1`. While `lo <= hi`, take `mid = Math.floor((lo + hi) / 2)`, return it if it holds the target, otherwise move `lo` to `mid + 1` or `hi` to `mid - 1`.
Try it now, free, no account needed
Every exercise on Scriptdrill is free to try. Open it on the practice page, solve it, and get instant feedback with a hint. The worked solution opens once you solve it or after two tries.
Open this exerciseMore exercises in Arrays and objects
- Group by a fieldFree
- Count by a fieldFree
- Remove duplicates by a fieldFree
- Split into chunksFree
- Zip two arraysFree
- Flatten one levelFree
- Pick some keysFree
- Sort by several keysFree
- Merge settingsFree
- Omit some keysFree
- Flatten to a depthFree
- Transpose a matrixFree
- Two numbers that add upFree
- Values in both arraysFree
- Rotate an arrayFree