Binary search, on index and on answer

Q: Why does the loop say while lo < hi and not lo <= hi?

Because the range lo to hi is half open: lo is the first index still in play and hi is the first index past it. When the two meet the range holds nothing, so there is nothing left to test and the loop is done. Writing lo <= hi with this initialisation gives the loop one extra turn, and on that turn mid can equal len(nums), which reads off the end of the array. Pick one convention, say which one you are using, and let every line follow from it.

Q: Should mid be (lo + hi) // 2 or lo + (hi - lo) // 2?

In Python the two are the same, because integers do not overflow. In Java, C++, or Go they are not: lo + hi can exceed the largest signed 32-bit integer on a big array and wrap to a negative number, which is the bug that sat in the JDK binary search for years. Writing lo + (hi - lo) // 2 costs nothing and is the habit to carry between languages. Say that out loud if the interviewer is working in one of those languages.

Q: What does binary search on the answer mean?

It means the range you search is not the input at all. You pick the smallest and largest answers that could possibly be right, then ask of a candidate answer: does this one work? For Koko Eating Bananas the range is eating speeds and the question is whether that speed clears the piles in time. The method applies whenever a candidate that works implies every larger candidate works too, which is the same flip-once condition as before.

Q: Why does my binary search loop forever?

Almost always because one branch fails to shrink the range. With floor division mid equals lo whenever hi is exactly one more than lo, so writing lo = mid in that branch assigns lo to itself and nothing moves. The fix is lo = mid + 1, which is sound because a no at mid rules mid itself out. The other common cause is using hi = mid in a loop whose condition is lo <= hi, where the two can sit equal forever.

Q: When should I use bisect instead of writing the loop?

In a real interview, write the loop once to show you can, then say you would reach for bisect in production code. bisect_left returns the first index whose value is at least the target, which is exactly this template. bisect_right returns the first index whose value is strictly greater, so bisect_right minus bisect_left counts how many copies of a value the array holds. Both take lo and hi arguments for searching a slice, and both accept a key function from Python 3.10 on.

Ask a yes-or-no question along a range where the answer flips exactly once. Binary search finds the flip, and half of what is left disappears with every question.

Problems worked on this page, and more to practise

Why does the loop say while lo < hi and not lo <= hi?

Because the range lo to hi is half open: lo is the first index still in play and hi is the first index past it. When the two meet the range holds nothing, so there is nothing left to test and the loop is done. Writing lo <= hi with this initialisation gives the loop one extra turn, and on that turn mid can equal len(nums), which reads off the end of the array. Pick one convention, say which one you are using, and let every line follow from it.

Should mid be (lo + hi) // 2 or lo + (hi - lo) // 2?

In Python the two are the same, because integers do not overflow. In Java, C++, or Go they are not: lo + hi can exceed the largest signed 32-bit integer on a big array and wrap to a negative number, which is the bug that sat in the JDK binary search for years. Writing lo + (hi - lo) // 2 costs nothing and is the habit to carry between languages. Say that out loud if the interviewer is working in one of those languages.

What does binary search on the answer mean?

It means the range you search is not the input at all. You pick the smallest and largest answers that could possibly be right, then ask of a candidate answer: does this one work? For Koko Eating Bananas the range is eating speeds and the question is whether that speed clears the piles in time. The method applies whenever a candidate that works implies every larger candidate works too, which is the same flip-once condition as before.

Why does my binary search loop forever?

Almost always because one branch fails to shrink the range. With floor division mid equals lo whenever hi is exactly one more than lo, so writing lo = mid in that branch assigns lo to itself and nothing moves. The fix is lo = mid + 1, which is sound because a no at mid rules mid itself out. The other common cause is using hi = mid in a loop whose condition is lo <= hi, where the two can sit equal forever.

When should I use bisect instead of writing the loop?

In a real interview, write the loop once to show you can, then say you would reach for bisect in production code. bisect_left returns the first index whose value is at least the target, which is exactly this template. bisect_right returns the first index whose value is strictly greater, so bisect_right minus bisect_left counts how many copies of a value the array holds. Both take lo and hi arguments for searching a slice, and both accept a key function from Python 3.10 on.