Implement binary search on a sorted array
Reported in Roblox USA engineering loops. Foundational search algorithm with clear loop invariants and edge cases.
Interview scenario
Context for Roblox candidates:
Return the index of target or -1 if absent. Discuss iterative vs recursive variants.
Model answer
Try answering aloud first
Cover trade-offs, structure, and a concrete example before revealing the baseline response.
How to frame this at Roblox: Connect your answer to measurable impact, clarity of thought, and trade-offs the team cares about. Below is a strong baseline response you can adapt with your own project examples.
Binary search halves the search space each step by comparing target with the middle element. Maintain lo and hi bounds; loop while lo <= hi.
function binarySearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}Complexity: O(log n) time, O(1) space iterative. Common bugs: integer overflow on (lo+hi)/2 in languages without safe mid calculation, infinite loops from incorrect bounds, off-by-one on empty arrays.
Extensions: first/last occurrence (lower/upper bound), search rotated array, and search in answer space (binary search on value, not index).
Discussion
Comments (0)
Share how this question came up in your loop, or add tips for others preparing.
Log in to comment on this question.