tag

#lower-bound

2 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Lower Bound

Lower Bound Lower bound finds the first index at which a value $x$ can be inserted in a sorted array while preserving order. It returns the smallest index $i$ such that $$ A[i] \ge x $$ If all elements are smaller than $x$, it returns $n$. This operation forms the basis of many ordered data structure queries, including range queries and duplicate handling. Problem Given a sorted array $A$ of...

Wiki › Algorithms › 01. Searching and Sorting › 12. Specialized Search and Sorted-Order Procedures ›

Branchless Lower Bound

Branchless Lower Bound Branchless lower bound computes the first position where a value is greater than or equal to a target, without using unpredictable branches. It follows the same logical structure as binary search but replaces control flow with arithmetic updates or conditional moves. The result is the same as standard lower bound. The benefit is improved performance on modern CPUs when branch misprediction is expensive. Problem Given a sorted...