How do you implement Binary Search correctly?

Short answer: Maintain inclusive or exclusive bounds consistently. Compute mid carefully (lo + (hi − lo) / 2) to avoid overflow. Decide whether you want lower-bound, upper-bound, or exact match before coding.

Complexity

Time O(log n), Space O(1).

Mistakes to avoid

• Off-by-one infinite loops
• Using (lo+hi)/2 overflow on large ints
• Mixing inclusive/exclusive bounds

State the loop invariant: “answer is always inside [lo, hi]”.