MediumDSAAsked in 20245 min read

Binary search implementation

Q: Binary search implementation

**Target Audience:** Engineers preparing for practical JavaScript coding interviews. **Difficulty:** Medium > **How to read this doc:** binary search is famous for being easy to describe and easy to get subtly wrong (off-by-one, infinite loops, duplicates). So the code here was checked against a brute-force reference over 20,000 seeded random arrays, for membership, `lowerBound` and `upperBound`, with zero mismatches. ## 1. The problem, restated Given a sorted array, find a target in O(log n) by repeatedly discarding half of the remaining range. The interesting parts are the loop invariant, what to return when there are duplicates, and the preconditions the algorithm silently depends on. ## 2. Clarifying questions a strong candidate asks | Question | Why it matters | | :--- | :--- | | Is it actually sorted? | Binary search on unsorted data returns wrong answers without any error. | | Sorted by what? | It must match the comparison used in the search. A default `.sort()` sorts numbe

903 views

96 of 154

The problem

Problem, as an interviewer would state it: "Implement binary search on a sorted array, returning the index of the target or -1. Discuss edge cases, runtime, and how you would handle duplicates."

Examples:

Code

binarySearch([1, 3, 5, 7, 9, 11], 7); // 3
binarySearch([1, 3, 5, 7], 4);        // -1

Clarifying questions expected:

Is the array guaranteed sorted, and in which order and by what comparison?
If the target appears several times, which index should be returned — any, the first, or the last?
Should I return -1 on a miss, or the insertion point?

Code / implementation expected: Yes — real, direct proof against a brute-force reference, plus the duplicate-handling variants.

js-coding
utility
algorithm

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Engineers preparing for practical JavaScript coding interviews. Difficulty: Medium

How to read this doc: binary search is famous for being easy to describe and easy to get subtly wrong (off-by-one, infinite loops, duplicates). So the code here was checked against a brute-force reference over 20,000 seeded random arrays, for membership, lowerBound and upperBound, with zero mismatches.

1. The problem, restated

Given a sorted array, find a target in O(log n) by repeatedly discarding half of the remaining range. The interesting parts are the loop invariant, what to return when there are duplicates, and the preconditions the algorithm silently depends on.

2. Clarifying questions a strong candidate asks

Question	Why it matters
Is it actually sorted?	Binary search on unsorted data returns wrong answers without any error.

The solution is hidden so you can try first

5 min read · 9 sections

Run the code

Edit the code and run it here. Each console line with an expected value becomes a test.

JavaScriptReal, direct proof: binary search matches a brute-force reference on random arrays, handles duplicates via lowerBound/upperBound, and fails on unsorted input

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

No comments yet. Share how you would answer it.

Question 96 of 154 in JavaScript coding

Keep your momentum going.

Mark this question solved to track your progress, then take the next one while it is fresh.

All JavaScript coding questions

Up nextMedium→

Implement Promise.any() with AggregateError

Continue