You're given a sorted array of numbers and a target value. Return the index of the target if it's in the array, or -1 if it isn't. This is the classic binary search — instead of scanning left to right (O(n)), you halve the search range on every step (O(log n)).
// Returns the index of `target` in `arr`, or -1 if not present.
// `arr` is sorted ascending. `arr` is not mutated.
function binarySearch(arr: number[], target: number): number;binarySearch([1, 3, 5, 7, 9, 11], 7); // 3
binarySearch([1, 3, 5, 7, 9, 11], 1); // 0 (first element)
binarySearch([1, 3, 5, 7, 9, 11], 11); // 5 (last element)
binarySearch([1, 3, 5, 7, 9, 11], 4); // -1 (not present)binarySearch([], 7); // -1 (empty array)
binarySearch([42], 42); // 0 (single element, hit)
binarySearch([42], 7); // -1 (single element, miss)
binarySearch([1, 2, 2, 2, 3], 2); // any of 1, 2, 3 — duplicates allowedMath.floor((low + high) / 2) is the obvious midpoint, but on very large arrays low + high can overflow safe-integer range in other languages. In JS that's mostly theoretical, but the low + Math.floor((high - low) / 2) form is the standard idiom you'll see in interviews.Array.prototype.indexOf. That's O(n) and defeats the purpose of the exercise.You'll write a function that finds a value in a sorted array by repeatedly cutting the search window in half — the canonical O(log n) lookup.
Think of looking up a word in a paper dictionary. You don't start at "A" and read every entry; you open to the middle, see whether the word you want is alphabetically before or after, and throw away the half that can't contain it. Then you do that again on what's left. Binary search is exactly that — applied to a sorted array. The "sorted" part is what gives you the right to discard half the array after a single comparison.
Hold two pointers, low and high, at the ends of the array. Compute mid = floor((low + high) / 2) — the index in the middle of the current window. Compare arr[mid] to the target. If they match, you're done. If arr[mid] is smaller than the target, the target (if it exists) must be to the right, so move low to mid + 1. If arr[mid] is larger, the target must be to the left, so move high to mid - 1. Repeat until you find it or the window empties.
Halving each step is what gets you from n comparisons (a left-to-right scan) down to about log₂(n) comparisons. For an array of a million elements, that's the difference between ~1,000,000 steps and ~20.
If you've only seen Array.prototype.indexOf, you might write the linear version:
function naiveSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}This is correct, and on a small array it's perfectly fine. But it ignores the gift the problem hands you: the array is sorted. A linear scan does the same work on [1, 2, 3, ..., 999999] as it does on a shuffled array — O(n) either way. Binary search exploits the order to skip vast stretches of the array each step. On n = 1,000,000, indexOf averages ~500,000 comparisons; binary search needs about 20.
There's also a subtler trap with linear scans on big inputs in real codebases: people reach for arr.indexOf(target) !== -1 inside another loop, and the outer O(n) quietly becomes O(n²). Knowing binary search exists is half the battle.
function binarySearch(arr, target) {
// Two pointers bounding the active search window, inclusive on both ends.
let low = 0;
let high = arr.length - 1;
// Loop while the window is non-empty. `low > high` means we've eliminated
// every position; the target isn't in the array.
while (low <= high) {
// Compute the midpoint of the window. The `low + (high - low) / 2` form
// (instead of `(low + high) / 2`) avoids integer overflow in languages
// with fixed-width ints. In JS it's mostly idiomatic, but worth using.
const mid = low + Math.floor((high - low) / 2);
if (arr[mid] === target) {
// Hit — return the index. (For duplicates, any matching index is correct.)
return mid;
}
if (arr[mid] < target) {
// Target is bigger than arr[mid], so it can only be to the right.
// Move `low` past `mid` — we already checked `mid` itself above.
low = mid + 1;
} else {
// arr[mid] > target. Target can only be to the left. Move `high`
// below `mid` for the same reason: `mid` is already ruled out.
high = mid - 1;
}
}
// Window emptied without finding the target.
return -1;
}
module.exports = { binarySearch };Two shifts from the naive version. First, the loop body does one comparison and then jumps — low = mid + 1 or high = mid - 1 — instead of advancing by 1. That's where the speedup comes from. Second, the + 1 / - 1 on the pointer updates is doing real work: it guarantees the window strictly shrinks every iteration, which is what makes the loop terminate. Forget the + 1 and you can land back on the same mid forever; you'll write an infinite loop. We'll see that gotcha below.
Trace binarySearch([1, 3, 5, 7, 9, 11, 13], 11).
Step by step:
low = 0, high = 6, so low <= high is true.mid = 0 + floor((6 - 0) / 2) = 3. arr[3] === 7. 7 !== 11, so it's not a hit. 7 < 11, so the target (if present) is to the right of index 3. Set low = mid + 1 = 4. The window is now [4, 6] — indices 4, 5, 6.low = 4, high = 6. 4 <= 6, continue.mid = 4 + floor((6 - 4) / 2) = 5. arr[5] === 11. 11 === 11, hit. Return 5.Two comparisons. A linear scan on the same input would have taken six (indices 0 through 5 before landing on 11).
Now trace a miss: binarySearch([1, 3, 5, 7, 9, 11, 13], 4).
mid = 3, arr[3] = 7. 7 > 4, so high = mid - 1 = 2. Window [0, 2].mid = 0 + floor(2/2) = 1. arr[1] = 3. 3 < 4, so low = 2. Window [2, 2].mid = 2. arr[2] = 5. 5 > 4, so high = 1. Window [2, 1].low = 2, high = 1. 2 <= 1 is false — exit loop. Return -1.The low > high exit condition is what makes "not found" terminate. Without + 1 / - 1, that window never goes empty.
Complexity. Time is O(log n) — the window shrinks by at least one element per step (and roughly halves), so after k steps the window size is at most ⌈n / 2^k⌉; the loop exits when that drops to 0. Space is O(1) — two integer pointers, regardless of input size.
low = mid instead of low = mid + 1. If arr[mid] isn't the target you've already checked it; the next window must exclude it. Forgetting the + 1 means a single-element window can pick the same mid again and the loop never terminates. Same trap with high = mid instead of high = mid - 1.(low + high) / 2 instead of Math.floor((low + high) / 2). JavaScript doesn't have integer division — 5 / 2 is 2.5. Indexing with a float yields undefined, which compares as not-equal-to-anything, and your loop converges weirdly. Always wrap in Math.floor (or use >> 1, the bitwise-shift trick, which also floors).while (low < high) instead of while (low <= high). With strict <, you stop one iteration too early — a single-element window never gets compared, so a one-element array hit returns -1. Use <= so the final candidate is checked.[5, 1, 9, 3] and you run binary search on it, you'll get garbage answers, not an error. If you're not sure the input is sorted, you have to scan-and-check or sort first — and once you've sorted, you've paid O(n log n), which is worse than just doing a linear search for one element.binarySearch(arr, target, low, high) is correct but adds a stack frame per step. On pathological inputs you can blow the call stack; the iterative two-pointer version uses O(1) space. Stick with the loop unless an interviewer specifically asks for the recursive form.high = mid - 1 and remember mid. At the end, low is the leftmost index where target would belong. This is how Array.prototype.findIndex would behave on a sorted array if it knew the array was sorted.[5, 6, 7, 1, 2, 3, 4] (sorted then rotated), one half of the window around mid is always sorted; you can detect which half and apply the standard left/right decision to it. Same O(log n); a classic follow-up.bisect). Replace arr[mid] === target with predicate(mid) and you've got the building block for "find the smallest x such that f(x) is true" — used for capacity-planning problems, optimisation, and lower_bound/upper_bound in C++ STL.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
You're given a sorted array of numbers and a target value. Return the index of the target if it's in the array, or -1 if it isn't. This is the classic binary search — instead of scanning left to right (O(n)), you halve the search range on every step (O(log n)).
// Returns the index of `target` in `arr`, or -1 if not present.
// `arr` is sorted ascending. `arr` is not mutated.
function binarySearch(arr: number[], target: number): number;binarySearch([1, 3, 5, 7, 9, 11], 7); // 3
binarySearch([1, 3, 5, 7, 9, 11], 1); // 0 (first element)
binarySearch([1, 3, 5, 7, 9, 11], 11); // 5 (last element)
binarySearch([1, 3, 5, 7, 9, 11], 4); // -1 (not present)binarySearch([], 7); // -1 (empty array)
binarySearch([42], 42); // 0 (single element, hit)
binarySearch([42], 7); // -1 (single element, miss)
binarySearch([1, 2, 2, 2, 3], 2); // any of 1, 2, 3 — duplicates allowedMath.floor((low + high) / 2) is the obvious midpoint, but on very large arrays low + high can overflow safe-integer range in other languages. In JS that's mostly theoretical, but the low + Math.floor((high - low) / 2) form is the standard idiom you'll see in interviews.Array.prototype.indexOf. That's O(n) and defeats the purpose of the exercise.You'll write a function that finds a value in a sorted array by repeatedly cutting the search window in half — the canonical O(log n) lookup.
Think of looking up a word in a paper dictionary. You don't start at "A" and read every entry; you open to the middle, see whether the word you want is alphabetically before or after, and throw away the half that can't contain it. Then you do that again on what's left. Binary search is exactly that — applied to a sorted array. The "sorted" part is what gives you the right to discard half the array after a single comparison.
Hold two pointers, low and high, at the ends of the array. Compute mid = floor((low + high) / 2) — the index in the middle of the current window. Compare arr[mid] to the target. If they match, you're done. If arr[mid] is smaller than the target, the target (if it exists) must be to the right, so move low to mid + 1. If arr[mid] is larger, the target must be to the left, so move high to mid - 1. Repeat until you find it or the window empties.
Halving each step is what gets you from n comparisons (a left-to-right scan) down to about log₂(n) comparisons. For an array of a million elements, that's the difference between ~1,000,000 steps and ~20.
If you've only seen Array.prototype.indexOf, you might write the linear version:
function naiveSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}This is correct, and on a small array it's perfectly fine. But it ignores the gift the problem hands you: the array is sorted. A linear scan does the same work on [1, 2, 3, ..., 999999] as it does on a shuffled array — O(n) either way. Binary search exploits the order to skip vast stretches of the array each step. On n = 1,000,000, indexOf averages ~500,000 comparisons; binary search needs about 20.
There's also a subtler trap with linear scans on big inputs in real codebases: people reach for arr.indexOf(target) !== -1 inside another loop, and the outer O(n) quietly becomes O(n²). Knowing binary search exists is half the battle.
function binarySearch(arr, target) {
// Two pointers bounding the active search window, inclusive on both ends.
let low = 0;
let high = arr.length - 1;
// Loop while the window is non-empty. `low > high` means we've eliminated
// every position; the target isn't in the array.
while (low <= high) {
// Compute the midpoint of the window. The `low + (high - low) / 2` form
// (instead of `(low + high) / 2`) avoids integer overflow in languages
// with fixed-width ints. In JS it's mostly idiomatic, but worth using.
const mid = low + Math.floor((high - low) / 2);
if (arr[mid] === target) {
// Hit — return the index. (For duplicates, any matching index is correct.)
return mid;
}
if (arr[mid] < target) {
// Target is bigger than arr[mid], so it can only be to the right.
// Move `low` past `mid` — we already checked `mid` itself above.
low = mid + 1;
} else {
// arr[mid] > target. Target can only be to the left. Move `high`
// below `mid` for the same reason: `mid` is already ruled out.
high = mid - 1;
}
}
// Window emptied without finding the target.
return -1;
}
module.exports = { binarySearch };Two shifts from the naive version. First, the loop body does one comparison and then jumps — low = mid + 1 or high = mid - 1 — instead of advancing by 1. That's where the speedup comes from. Second, the + 1 / - 1 on the pointer updates is doing real work: it guarantees the window strictly shrinks every iteration, which is what makes the loop terminate. Forget the + 1 and you can land back on the same mid forever; you'll write an infinite loop. We'll see that gotcha below.
Trace binarySearch([1, 3, 5, 7, 9, 11, 13], 11).
Step by step:
low = 0, high = 6, so low <= high is true.mid = 0 + floor((6 - 0) / 2) = 3. arr[3] === 7. 7 !== 11, so it's not a hit. 7 < 11, so the target (if present) is to the right of index 3. Set low = mid + 1 = 4. The window is now [4, 6] — indices 4, 5, 6.low = 4, high = 6. 4 <= 6, continue.mid = 4 + floor((6 - 4) / 2) = 5. arr[5] === 11. 11 === 11, hit. Return 5.Two comparisons. A linear scan on the same input would have taken six (indices 0 through 5 before landing on 11).
Now trace a miss: binarySearch([1, 3, 5, 7, 9, 11, 13], 4).
mid = 3, arr[3] = 7. 7 > 4, so high = mid - 1 = 2. Window [0, 2].mid = 0 + floor(2/2) = 1. arr[1] = 3. 3 < 4, so low = 2. Window [2, 2].mid = 2. arr[2] = 5. 5 > 4, so high = 1. Window [2, 1].low = 2, high = 1. 2 <= 1 is false — exit loop. Return -1.The low > high exit condition is what makes "not found" terminate. Without + 1 / - 1, that window never goes empty.
Complexity. Time is O(log n) — the window shrinks by at least one element per step (and roughly halves), so after k steps the window size is at most ⌈n / 2^k⌉; the loop exits when that drops to 0. Space is O(1) — two integer pointers, regardless of input size.
low = mid instead of low = mid + 1. If arr[mid] isn't the target you've already checked it; the next window must exclude it. Forgetting the + 1 means a single-element window can pick the same mid again and the loop never terminates. Same trap with high = mid instead of high = mid - 1.(low + high) / 2 instead of Math.floor((low + high) / 2). JavaScript doesn't have integer division — 5 / 2 is 2.5. Indexing with a float yields undefined, which compares as not-equal-to-anything, and your loop converges weirdly. Always wrap in Math.floor (or use >> 1, the bitwise-shift trick, which also floors).while (low < high) instead of while (low <= high). With strict <, you stop one iteration too early — a single-element window never gets compared, so a one-element array hit returns -1. Use <= so the final candidate is checked.[5, 1, 9, 3] and you run binary search on it, you'll get garbage answers, not an error. If you're not sure the input is sorted, you have to scan-and-check or sort first — and once you've sorted, you've paid O(n log n), which is worse than just doing a linear search for one element.binarySearch(arr, target, low, high) is correct but adds a stack frame per step. On pathological inputs you can blow the call stack; the iterative two-pointer version uses O(1) space. Stick with the loop unless an interviewer specifically asks for the recursive form.high = mid - 1 and remember mid. At the end, low is the leftmost index where target would belong. This is how Array.prototype.findIndex would behave on a sorted array if it knew the array was sorted.[5, 6, 7, 1, 2, 3, 4] (sorted then rotated), one half of the window around mid is always sorted; you can detect which half and apply the standard left/right decision to it. Same O(log n); a classic follow-up.bisect). Replace arr[mid] === target with predicate(mid) and you've got the building block for "find the smallest x such that f(x) is true" — used for capacity-planning problems, optimisation, and lower_bound/upper_bound in C++ STL.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.