new | ask | show | jobs
scuol 19 hours 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 18 hours ago  [ - ]

Godspeed, 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...