4 ms·
The way I always remember leftmost and rightmost binary search (the C++ equivalents-ish of lower_bound and upper_bound) is to always have a "prior best" and the
by scuol 1y ago
The way I always remember leftmost and rightmost binary search (the C++ equivalents-ish of lower_bound and upper_bound) is to always have a "prior best" and then move the bounds according to the algo
while (l < r)
{
//find the midpoint
auto mp = l + (l-r)/2;
if (nums[mp] == target)
{
prior = target;
#ifdef upper_bound
l = target + 1; // move the left bound up, maybe there's more up there we can look for!
#else
//lower bound, we found the highest known instance of target, but let's look in the exclusive left half a bit more
r = target - 1;
#endif
}
excuse the terrible formatting, it's been a long day grinding leetcode after getting laid off...
- hiAndrewQuinn 1y agoGodspeed, fellow LeetCoder. I'm not currently grinding but I still have my handful of practice problems in active Anki rotation. I have my rightmost code at part III of the miniseries, [1]. It loks quite similar, but I save the -1 for the very end return. def rightmost_bsearch(L, T): l, r = 0, len(L) while l < r: # Loop invariants. Always true! Comment out in production! for somewhat_smol in L[0:l]: assert somewhat_smol <= T # Note: Weak inequality now. for lorg in L[r:len(L)]: assert lorg > T mid = (l + r) // 2 if L[mid] > T: r = mid else: l = mid + 1 return r - 1 # return the first element AFTER L[r:len(L)]. (It should technically be BEFORE, I guess. If it helps all rightmost bsearches are also leftmost bsearches on the reversed array, so AFTER is secretly not wrong) [1]: https://hiandrewquinn.github.io/til-site/posts/binary-search-isn-t-about-search-iii-loop-invariant-of-rightmost-element-search/ https://hiandrewquinn.github.io/til-site/posts/binary-search...