Bound to love lower_bound.

Understanding lower_bound's algorithmic behaviour in C++

This medium-difficulty C++ language question tests your grasp of the standard library's lower_bound algorithm and its performance guarantees. Interviewers ask it to confirm you know not just what the function does, but why it performs the way it does — a distinction that matters in systems where latency is critical.

Lower_bound is a cornerstone tool for binary search and range queries in sorted containers. Answering correctly requires you to understand the precondition (the container must be sorted), the semantics of "the first element not less than the search value," and crucially, the number of comparisons the algorithm makes relative to the input size. Candidates should reason about how the search space shrinks with each iteration and express their answer in standard algorithmic notation.

• Binary search and divide-and-conquer strategies
• Preconditions and their role in algorithmic guarantees
• Expressing complexity in terms of container size