Binary Search

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)).

Signature

// 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;

Examples

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 allowed

Notes

• The input is sorted ascending. You may rely on that — don't sort it yourself, and don't write a version that works on unsorted input.
• Return any matching index for duplicates. If the target appears multiple times, returning any of those indices is correct. There's a stricter "leftmost index" variant — see Going further in the solution.
• Iterative is preferred. A recursive version works, but the iterative two-pointer form is shorter and avoids stack frames. Both are accepted; tests don't care which.
• Mind the midpoint. Math.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.
• Don't use Array.prototype.indexOf. That's O(n) and defeats the purpose of the exercise.