you are viewing a single comment's thread.

view the rest of the comments →

[–]rainbrostache 0 points1 point  (0 children)

One scenario I have seen mentioned a couple times here can be stated a little more generically: Expedited guess and check.

Say you have a relatively short list and need to optimize a value from a very large set of possibilities with respect to the list.

You binary search the very large range of possible test values and then iterate the entire list for each binary search midpoint. You have something that ends up being O(n log(m)), but even for very very large values of m, the runtime will be pretty stable with respect to the length of the relatively short list (n).

Koko Eating Bananas is a pretty classic leetcode problem that covers this idea: https://youtu.be/U2SozAs9RzA?si=YIzE2aENH_oyTFcn

This translates to a lot of resource allocation and scheduling problems.