I was working through this problem on leetcode https://leetcode.com/problems/leftmost-column-with-at-least-a-one/ and I cant think of an intuitive answer.
Why is the right (or high) pointer sometimes set to mid - 1, and why is it sometimes correct to set to mid?
I am aware that we must always set left = mid + 1 because of integer division. When only two elements remain, we need to set mid + 1 to avoid an infinite loop.
But what are the cases to use right = mid - 1, vs right = mid?
Thanks.
Let's say you are doing binary search on a sequence like below
.....0, 0, 0, 0, 1, 1, 1, 1, ....
Your decision function fn returns true if the value holds true for 1.
Now consider your target is to find the last position for 0. In each step of binary search, we will reduce search space such that we are certain the position is within the range.
If fn returns true for mid you know that the last position for 0 will be less than mid (because you want the last occurrence of 0 which must be before the first occurrence of 1). So, you will update right=mid-1. If fn return false left=mid.
Now consider your target is to find the first occurrence for 1.
Now if fn returns true you will update right=mid because you know the first occurrence of 1 will be on this position or left of it. In this case, if fn returns false, you will need to update left=mid+1.