Templates

These templates come from LeetCode.

Tips

The tip below comes from LeetCode 278. First Bad Version.

If you are setting mid = (left+right) / 2, you have to be very careful. Unless you are using a language that does not overflow such as Python, left + right could overflow. One way to fix this is to use left + (right-left)/2 instead.

If you fall into this subtle overflow bug, you are not alone. Even Jon Bentley's own implementation of binary search had this overflow bug and remained undetected for over twenty years.