I'm reading the Competitive Programmer’s Handbook: https://cses.fi/book/book.pdf
On the pages 32 and above (PDF pp 42), there are mentioned the Method 2 for Binary Search, which I'm not sure I understand completely. They then modify this slightly to find the minimum value such that function ok() is true, and try to find the maximum in an array. I don't intuitively understand what's going on here. Is there any intuitive explanation?
int k = 0;
for (int b = n/2; b >= 1; b /= 2) {
while (k+b < n && array[k+b] <= x) k += b;
}
if (array[k] == x) {
// x found at index k
}
Finding the minimum value that works for function ok
int x = -1;
for (int b = z; b >= 1; b /= 2) {
while (!ok(x+b)) x += b;
}
int k = x+1;
Find the maximum value for a function that is first increasing and then decreasing
int x = -1;
for (int b = z; b >= 1; b /= 2) {
while (f(x+b) < f(x+b+1)) x += b;
}
int k = x+1;
The explanations in the book are very good! I will use them as a starting point.
Imagine you have a dictionary, you open it on the first page (int k = 0;), and you're looking for a word in the dictionary (x).
The invariant assumptions are:
i, 0 < i < n: array[i-1] <= array[i]),array[k]) is never greater than the word you're looking for (array[k] <= x is always true).b is your guess about how many pages away from the answer you are. In binary search, you always guess the half of the biggest possible distance. Initially, the biggest possible distance is the length of your dictionary n. So initially, you take half of the length of the dictionary as your guess - int b = n/2;.
You move your current position k ahead the guessed number of pages b as long as you can, i.e. as long as assumption 2. is satisfied. Then you guess again, halving your guessed distance b.
When b becomes 1, you've found the page in the dictionary you've been looking for. Either array[k] == x - the dictionary contains the word on page k, or there is no such word in your dictionary.
The latter examples with !ok(x+b) and f(x+b) < f(x+b+1) are essentially the same as the one with array[k+b] <= x.
Imagine you have an array with all possible values of !ok(i) in array[i] (or all possible values of f(i) < f(i+1) in array[i]). Then you do a binary search over array the same way as with array[k+b] <= x.
Note that the book assumes ok(i) and f(i) work for any i, while the array size is limited and has to be checked: k+b < n, where n is the array size.
Note on the code style in the book:
In competitive programming, where you have a very limited amount of time to solve a large number of algorithmic problems and never look at the code again, it's okay to use short variable names, no comments, etc. It's also common to see many #DEFINE directives - see for example https://gist.github.com/kodekracker/e09f9d23573f117a5db0 .
I understand how this may be very surprising. Trading code readability for implementation speed so much is unacceptable in the world of long-term professional projects.