Блог пользователя Raythroughspace

How does this loop work?
Автор Raythroughspace, история, 5 лет назад, По-английски

How does this loop work in C++? Is there an equivalent while loop?

int firstTrue(int lo, int hi, function<bool(int)> f) {
	for (hi ++; lo < hi; ) {
		int mid = lo+(hi-lo)/2;
		if f(mid) hi = mid;
		else lo = mid+1;
	}
	return lo;
}
  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I don't understand what you're trying to ask.

The loop you have is an infinite loop if hi >= lo, so the equivalent while loop is while (true) {}.

Please elaborate on what you want the loop to do

→ Ответить
»
5 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

It is just a simple binary search. This is an equivalent code:

int first_true(int l, int r, function<bool (int)> f) {
    while (l < r) {
        int m = l + (r - l)/2;
        if (f(m)) r = m;
        else l = m + 1;
    }
    return l;
}

(Sorry spoilers are broken)

This is a binary search. I dislike the way that r is incremented in the beggining of the function, so I removed it. This will only work if there exists an index $$$x$$$ such that for all $$$l \leqslant i \lt x$$$, $$$f(i) = 0$$$ and for all $$$x \leqslant i \lt r$$$, $$$f(i) = 1$$$. We want to find $$$x$$$. We will keep an invariant, that $$$l \leqslant x \leqslant r$$$. Let $$$m = (l + r)/2$$$. If $$$f(m) = 1$$$, it means that $$$x \leqslant m$$$, thus, the invariant still holds after the operation $$$r = m$$$. Otherwise, $$$f(m) = 0$$$, which means that $$$x$$$ is strictly greater than $$$l$$$, thus, after the operation $$$l = m + 1$$$, the invariant still holds. Notice that after each turn $$$r - l$$$ will decrease in at least one, which implies that it won't get stuck in an infinite loop. This method is called binary search because it takes logarithm time to compute $$$x$$$. You can read more about complexity online.

EDIT: Added detailed explanation

→ Ответить