AlgoViz
HomeBinary Search

Lower Bound

Easy

First index with a[i] ≥ x

In simple words

Find the first spot where the value is big enough (at least x) by cutting the list in half each time.

The idea

The lower bound is the leftmost position whose value is at least x. Shrink toward the first index that satisfies a[i] ≥ x.

1
2
2
3
0
1
2
3
x2

Step 1 of 4. Brute force: scan left to right for the first value at least 2. Values: 1, 2, 2, 3. x 2.

1/4
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:
1
Explanation:
First index whose value is >= 2.

Example 2

Input:
nums = [3, 5, 8], x = 9
Output:
3
Explanation:
Nothing is >= 9, so answer is n = 3.

Example 3

Input:
nums = [1, 2, 3], x = 0
Output:
0
Explanation:
Everything is >= 0, so index 0.

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

Finished the walkthrough? Add it to your streak.