1

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;
Fire Lancer
  • 29,364
  • 31
  • 116
  • 182
herophant
  • 642
  • 7
  • 16
  • 3
    Note that the book you read is full of bad advice. First of all, [don't include ``](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h). Don't use single-letter variable names, use descriptive words about what they're for. Indentation and spaces and empty lines make code much easier to read and understand, as does comments explaining the often obfuscated parts needed in competitive programming. If you want to learn C++ then [get a few *good* books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282). – Some programmer dude May 13 '19 at 08:22
  • I don't want to learn C++ per se, and I'm not a beginner and understand your points. I want to get used to algorithms used to solve problems such as those in leetcode, and was told this was a good book to learn them. I didn't know what dynamic programming was yesterday and this has a good overview of everything, although the C++ advice may not be the best. – herophant May 13 '19 at 08:26
  • The explanations in the article are pretty good. It's not easy to add much to them. – molbdnilo May 13 '19 at 08:35
  • Might be worth going through it step by step on paper. Write out an array of say 20 numbers, then go through step by step to see how the variables are changing. – Fire Lancer May 13 '19 at 09:03
  • @herophant There are many good books about algorithms, like *Introduction to Algorithms*. Algorithms are language agnostic, and you don't need to learn bad programming habits in order to learn algorithms. – L. F. May 13 '19 at 09:32

1 Answers1

2

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:

  1. words in the dictionary are in non-decreasing order (for every i, 0 < i < n: array[i-1] <= array[i]),
  2. the word you're currently looking at (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.

Miłosz Łakomy
  • 996
  • 5
  • 12