Làm sao tránh lỗi infinite loop trong Binary Search?

Cách tránh lỗi là chọn một convention rõ ràng rồi giữ invariant tới cuối.

• Với inclusive boundary [left, right], loop là while (left <= right), nếu mid quá nhỏ thì left = mid + 1, nếu quá lớn thì right = mid - 1.
• Không update left = mid hoặc right = mid trong convention này vì có thể đứng yên khi còn 1-2 phần tử.
• Tính mid = left + Math.floor((right - left) / 2) để tránh overflow trong Java/C++.
• Với bài tìm lower_bound/answer space, hãy định nghĩa predicate monotonic và quyết định cuối cùng trả left hay right trước khi code.