AlgoViz
HomeBinary Search

Upper Bound

Easy

First index with a[i] > x

In simple words

Find the first value that is strictly bigger than x, halving the list each step.

The idea

The upper bound is the leftmost position whose value is strictly greater than x — the same search with a strict comparison.

1
2
2
3
0
1
2
3
x2

Step 1 of 6. Brute force: scan left to right for the first value greater than 2. Values: 1, 2, 2, 3. x 2.

1/6
Brute force
timeO(n)spaceO(1)

Scan for first > x.

1let ans = n;2for (let i = 0; i < n && ans === n; i++)3  if (nums[i] > x) ans = i;4return ans;

Input

array
[1, 2, 2, 3]

Memory

i
—
x
2

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 2, 2, 3], x = 2
Output:
3
Explanation:
First index strictly greater than 2.

Example 2

Input:
nums = [3, 5, 8], x = 5
Output:
2
Explanation:
Index just past the 5.

Example 3

Input:
nums = [1, 2, 3], x = 3
Output:
3
Explanation:
Nothing exceeds 3, so answer is n = 3.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.