{"id":493,"date":"2025-07-02T18:36:04","date_gmt":"2025-07-02T13:06:04","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=493"},"modified":"2025-07-02T18:36:50","modified_gmt":"2025-07-02T13:06:50","slug":"implement-upper-bound","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/implement-upper-bound\/","title":{"rendered":"Implement Upper Bound"},"content":{"rendered":"\n

In a sorted<\/strong> array arr[]<\/code>, the upper bound of x<\/code><\/strong> is the index of the first element that is strictly greater than x<\/code><\/strong>.
If every element in the array is \u2264 x<\/code>, the conventional upper-bound position is n<\/code> (one past the last index).<\/p>\n\n\n\n

Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n

\n

Example<\/strong>
arr = [1, 2, 4, 4, 6], x = 4<\/code>
Upper bound<\/em> \u2192 index 4<\/code> (value 6<\/code>), because indices 0\u20133<\/code> are \u2264 4<\/code> and index 4<\/code> is the first > 4<\/code>.<\/p>\n<\/blockquote>\n\n\n\n

Upper-bound queries power range searches, frequency counts, and insertion-point calculations. A tailored binary-search achieves this in logarithmic time.<\/p>\n\n\n

\n\t\t\t
\n\t\t\t\t
Contents:<\/div>\n\t\t\t\t
\n\t\t\t
\n\t\t\t\u00a0[show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div>
\n\t\t\t
\n\t\t\t\t