DSA-060 · First true boundary for value >= target

Search Insert Position — Lower Bound

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 22037 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the smallest index i such that nums[i]>=target in a nondecreasing int array. If no such index exists, return nums.length. This is the stable insertion position before all equal values.

nums is nonnull, nondecreasing, and has at most 100,000 elements. Sortedness is a precondition rather than a runtime O(n) validation. Duplicates and Integer.MIN_VALUE/MAX_VALUE are valid.
Return a boundary in [0,n], not necessarily an existing element index. Return zero for an empty array, zero when every value is already large enough, and n when every value is too small.
No input entry changes. null throws NullPointerException. The contract is first not-less, not any equality, upper bound, or a unique-value-only search.

Examples

Input: [1,2,2,4], target=2
Output: 1
Equality at mid=2 keeps right=2, then equality at index 1 keeps right=1; the earlier boundary is found.
Input: [1,2,4], target=5
Output: 3
The insertion boundary after the array is valid but must not be indexed.
Input: [], target=9
Output: 0
There is one empty-array insertion boundary.

Before you start

Half-open binary-search intervals
Nondecreasing predicates with duplicate values

Recognize the structure

The predicate nums[i]>=target is false then true along a sorted array. We need its transition boundary, so equality does not finish the search. A matching value may have earlier equal occurrences.

Try before revealing

Hint 1

Think of each index as answering whether its value is at least target.

Hint 2

The true region starts somewhere between zero and n, inclusive.

Hint 3

Move left past too-small midpoints; keep an eligible midpoint by setting right=mid.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Count the initial too-small prefix

Advance an index while nums[i]<target. For [1,2,2,4], target=2, skip only index 0 and stop at 1. If all values are smaller, stop at n. This O(n)-time, O(1)-space scan directly defines the desired first boundary.

Improve the baseline

Search n+1 possible boundaries

Initialize left=0,right=n. The answer can be n, which represents the all-false case; midpoint probes still always index real elements.

Maintain certified sides

All indices below left are <target, and all indices at or above right are >=target. A too-small midpoint certifies the entire prefix through mid; an eligible midpoint certifies the suffix starting at mid.

Converge without an early equality return

Use left=mid+1 for a too-small value and right=mid otherwise. At left==right the certified sides meet, giving the first eligible boundary.

Why it is correct

Initialization

The prefix before zero and suffix at/after n are empty, so both side claims hold, and the answer lies in [left,right].

Preservation

Sortedness extends nums[mid]<target to every earlier index, or nums[mid]>=target to every later index. Each update preserves both certified sides and keeps the transition boundary between the new bounds.

Termination

The interval shrinks until left==right. Every earlier index is too small and every existing index at or after the boundary is eligible, so the returned boundary is minimal, including n.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.Objects;

public final class Solution {
    public static int lowerBound(int[] nums, int target) {
        Objects.requireNonNull(nums, "nums");
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left;
    }
    public static int baseline(int[] nums, int target) {
        Objects.requireNonNull(nums, "nums");
        int i = 0;
        while (i < nums.length && nums[i] < target) i++;
        return i;
    }
}

Read the meaningful blocks

Boundary versus element

right=n is a legal boundary; the loop probes only mid<n. Return left even when it equals n.

Equality moves right

The else branch includes equality. Returning mid immediately would violate first-occurrence stability.

No target+1 arithmetic

The method compares values directly and is safe at either int extreme.

Complexity

Binary lower bound uses O(log(n+1)) time and O(1) auxiliary space; it performs no insertion and allocates no modified array.

The baseline scans O(n) elements with O(1) space. Actually inserting into a fixed array requires shifting/copying O(n) values, a separate operation.

Exact-state walkthroughs

Reveal normal and boundary traces

Equality moves toward the first duplicate

Input: {"nums":[1,2,2,4],"target":2} · Lower-bound boundary: 1

Step 1 of 5: Initialize the half-open element interval.

The first not-less boundary remains in [left,right], including n.

Lower bound — certified prefix and suffix

Unresolved boundary range: [0, 4]. Phase: search. Target: 2.

index 01retained element
index 12retained element
index 22retained element
index 34retained element

Highlight marks the last probed element, which may have just been discarded. The answer is a boundary, so n is a legal result even though it is not an element index. Certified sides meet when the two boundaries converge.

State after this step
Variable	Value
values	`[1,2,2,4]`
target	`2`
left	`0`
right	`4`
bounds	`"half-open"`
phase	`"search"`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     public static int lowerBound(int[] nums, int target) {
 5         Objects.requireNonNull(nums, "nums");
 6         int left = 0, right = nums.length;
 7         while (left < right) {
 8             int mid = left + (right - left) / 2;
 9             if (nums[mid] < target) left = mid + 1;
10             else right = mid;
11         }
12         return left;
13     }
14     public static int baseline(int[] nums, int target) {
15         Objects.requireNonNull(nums, "nums");
16         int i = 0;
17         while (i < nums.length && nums[i] < target) i++;
18         return i;
19     }
20 }
21

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Initialize the half-open element interval.
The first not-less boundary remains in [left,right], including n.
values
[1,2,2,4]
target
2
left
0
right
4
bounds
"half-open"
phase
"search"
Retain the eligible midpoint on the right boundary.
Sorted order proves the discarded side cannot contain the first eligible boundary. The interval strictly shrinks.
values
[1,2,2,4]
target
2
left
0
right
2
bounds
"half-open"
phase
"search"
before
[0,4]
mid
2
probeValue
2
found
false
Retain the eligible midpoint on the right boundary.
Sorted order proves the discarded side cannot contain the first eligible boundary. The interval strictly shrinks.
values
[1,2,2,4]
target
2
left
0
right
1
bounds
"half-open"
phase
"search"
before
[0,2]
mid
1
probeValue
2
found
false
Discard the too-small prefix through mid.
Sorted order proves the discarded side cannot contain the first eligible boundary. The interval strictly shrinks.
values
[1,2,2,4]
target
2
left
1
right
1
bounds
"half-open"
phase
"search"
before
[0,1]
mid
0
probeValue
1
found
false
Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
result
1

After-end insertion boundary

Input: {"nums":[1,2,4],"target":5} · Lower-bound boundary: 3

Step 1 of 4: Initialize the half-open element interval.

The first not-less boundary remains in [left,right], including n.

Lower bound — certified prefix and suffix

Unresolved boundary range: [0, 3]. Phase: search. Target: 5.

index 01retained element
index 12retained element
index 24retained element

State after this step
Variable	Value
values	`[1,2,4]`
target	`5`
left	`0`
right	`3`
bounds	`"half-open"`
phase	`"search"`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     public static int lowerBound(int[] nums, int target) {
 5         Objects.requireNonNull(nums, "nums");
 6         int left = 0, right = nums.length;
 7         while (left < right) {
 8             int mid = left + (right - left) / 2;
 9             if (nums[mid] < target) left = mid + 1;
10             else right = mid;
11         }
12         return left;
13     }
14     public static int baseline(int[] nums, int target) {
15         Objects.requireNonNull(nums, "nums");
16         int i = 0;
17         while (i < nums.length && nums[i] < target) i++;
18         return i;
19     }
20 }
21

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Initialize the half-open element interval.
The first not-less boundary remains in [left,right], including n.
values
[1,2,4]
target
5
left
0
right
3
bounds
"half-open"
phase
"search"
Discard the too-small prefix through mid.
Sorted order proves the discarded side cannot contain the first eligible boundary. The interval strictly shrinks.
values
[1,2,4]
target
5
left
2
right
3
bounds
"half-open"
phase
"search"
before
[0,3]
mid
1
probeValue
2
found
false
Discard the too-small prefix through mid.
Sorted order proves the discarded side cannot contain the first eligible boundary. The interval strictly shrinks.
values
[1,2,4]
target
5
left
3
right
3
bounds
"half-open"
phase
"search"
before
[2,3]
mid
2
probeValue
4
found
false
Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
result
3

Empty array has boundary zero

Input: {"nums":[],"target":9} · Lower-bound boundary: 0

Step 1 of 2: Initialize the half-open element interval.

The first not-less boundary remains in [left,right], including n.

Lower bound — certified prefix and suffix

Unresolved boundary range: [0, 0]. Phase: search. Target: 9.

Empty array — no probeable elements.

State after this step
Variable	Value
values	`[]`
target	`9`
left	`0`
right	`0`
bounds	`"half-open"`
phase	`"search"`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     public static int lowerBound(int[] nums, int target) {
 5         Objects.requireNonNull(nums, "nums");
 6         int left = 0, right = nums.length;
 7         while (left < right) {
 8             int mid = left + (right - left) / 2;
 9             if (nums[mid] < target) left = mid + 1;
10             else right = mid;
11         }
12         return left;
13     }
14     public static int baseline(int[] nums, int target) {
15         Objects.requireNonNull(nums, "nums");
16         int i = 0;
17         while (i < nums.length && nums[i] < target) i++;
18         return i;
19     }
20 }
21

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Initialize the half-open element interval.
The first not-less boundary remains in [left,right], including n.
values
[]
target
9
left
0
right
0
bounds
"half-open"
phase
"search"
Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
result
0

Test the contract

Input: []
Output: 0
Empty boundary.
Input: [2,2,2], target=2
Output: 0
All equal.
Input: [1,3], target=2
Output: 1
Between existing values.
Input: [MIN,MAX], target=MAX
Output: 1
Extreme equality.
Input: [1,2], target=3
Output: 2
After-end boundary.

Common mistakes and counterexamples

Return an arbitrary equal midpoint

Counterexample: [2,2,2,2], target=2 could return 2 instead of boundary 0.

Retain mid on the eligible side with right=mid.

Dereference the final boundary unconditionally

Counterexample: [1,2], target=3 returns n=2, which is outside element indices.

Check boundary<n before using nums[boundary].

Treat lower bound as upper bound

Counterexample: For [1,2,2], target=2, lower bound is 1 while upper bound is 3.

Choose >=target versus >target explicitly.

Claim insertion is logarithmic

Counterexample: Finding boundary 0 is logarithmic, but shifting a full array takes linear work.

Separate boundary lookup cost from data movement.

Follow-ups

Implement upper bound.

Change the too-small condition to nums[mid]<=target. The result is the first strictly greater index and preserves the same interval proof.

Count values in [a,b].

If a<=b, compute upperBound(b)−lowerBound(a). Do not implement upperBound(b) through b+1 when b can be Integer.MAX_VALUE.

Use Arrays.binarySearch.

Its equality result need not be the first duplicate. A negative return encodes an insertion point for absence, but the API is not a replacement for a duplicate-aware lower-bound routine.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 118/20,000 characters

Self-review

I distinguish a returnable boundary n from an indexable element.I maintain strict < on the left and >= on the right.Equality continues the search toward the first eligible position.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Binary search: candidate intervals and monotone feasibility

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-16 · Original teaching content and implementations authored for AceYourInterviews. Standard problem names do not imply company-frequency or external platform-difficulty claims.