DSA-059 · Exact lookup in a half-open candidate interval

Binary Search — Exact Lookup

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 an index containing target in a nondecreasing int array, or −1 when absent. If duplicates exist, any matching index is valid. Do not change the array.

nums must be nonnull and contain at most 100,000 ints in nondecreasing order; duplicates and all int extremes are allowed. Sortedness and the size bound are preconditions, not scanned validations, preserving logarithmic lookup.
Return any index i with nums[i]==target when a match exists, otherwise −1. An empty array returns −1. No first-occurrence or last-occurrence guarantee is made.
Both implementations are read-only; null throws NullPointerException. Unsorted arrays and concurrent changes are outside the contract. Array indices use a half-open interval [left,right).

Examples

Input: [1,3,5,7,9], target=7
Output: 3
mid=2 is too small; retain [3,5), then compare index 4 and retain [3,4).
Input: [2,2,2,2], target=2
Output: Any of 0,1,2,3; this Java method returns 2
A first-index oracle would wrongly reject this valid result.
Input: [], target=8
Output: −1
The initial interval is already empty.

Before you start

Nondecreasing array order and integer indices
Half-open ranges and loop invariants

Recognize the structure

Sorted order lets one comparison eliminate every candidate on one side. This is an existence-and-witness task, so equality may return immediately; a lower-bound task must continue left on equality instead.

Try before revealing

Hint 1

What sorted-order fact excludes all values before a midpoint that is too small?

Hint 2

Choose one interval convention and state whether right is an index or a boundary.

Hint 3

Use [0,n), return on equality, otherwise set left=mid+1 or right=mid; an empty interval means absent.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Scan for a matching value

Read indices from zero to n−1 and return the first equality, or −1. For [1,3,5,7,9], target=7 requires four comparisons and returns 3. It is a valid O(n)-time, O(1)-workspace baseline, although its first-match behavior is stronger than the any-match API and is not required of the optimized solution.

Improve the baseline

Define the candidate set

Start left=0,right=n; candidates are exactly indices in [left,right). right=n is a boundary, not an index to dereference.

Discard a proven impossible half

Compute mid=left+(right−left)/2. If nums[mid]<target, every index through mid is too small, so left=mid+1. If nums[mid]>target, mid and all later indices are too large, so right=mid.

Separate equality and exhaustion

Return mid immediately on equality. Otherwise the interval shrinks; when left==right it contains no candidates, so return −1.

Why it is correct

Initial coverage

Every possible matching index lies in [0,n). Bounds obey 0<=left<=right<=n.

Preservation

Sortedness justifies excluding [left,mid] after a smaller value, or [mid,right) after a larger one. No matching index is removed unless the method returns a valid equality witness.

Progress and result

While left<right, mid lies inside the interval. Both updates strictly decrease its nonnegative length, at least halving the retained candidate count up to rounding. At exhaustion the invariant rules out every index; equality returns a valid original index without writes.

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 search(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) return mid;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return -1;
    }
    public static int baseline(int[] nums, int target) {
        Objects.requireNonNull(nums, "nums");
        for (int i = 0; i < nums.length; i++) if (nums[i] == target) return i;
        return -1;
    }
}

Read the meaningful blocks

Half-open endpoints

Initialize right=n and loop on left<right. Do not mix this with closed right=n−1 or right=mid−1.

Safe midpoint

left+(right−left)/2 avoids adding two possibly large index boundaries. nums[mid] is safe because mid<right<=n.

Any-match return

Equality is sufficient for this contract. Duplicates need no scan or special branch, and no array value arithmetic is used.

Complexity

Optimized lookup takes O(log(n+1)) time and O(1) auxiliary space, including the empty case. Sortedness validation would require O(n) work and is deliberately a precondition.

The linear baseline takes O(n) worst-case time and O(1) space. Both preserve every array entry and allocate no returned collection.

Exact-state walkthroughs

Reveal normal and boundary traces

Target at the upper end

Input: {"nums":[1,3,5,7,9],"target":7} · Returned index: 3

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

Any target occurrence remains inside [left,right).

Exact lookup — retained element interval

Candidate element interval: [0, 5). Phase: search. Target: 7.

index 01retained element
index 13retained element
index 25retained element
index 37retained element
index 49retained element

Highlight marks the last probed element, which may have just been discarded. Only indices inside the retained interval remain candidates unless a match has already been found.

State after this step
Variable	Value
values	`[1,3,5,7,9]`
target	`7`
left	`0`
right	`5`
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 search(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) return mid;
10             if (nums[mid] < target) left = mid + 1;
11             else right = mid;
12         }
13         return -1;
14     }
15     public static int baseline(int[] nums, int target) {
16         Objects.requireNonNull(nums, "nums");
17         for (int i = 0; i < nums.length; i++) if (nums[i] == target) return i;
18         return -1;
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.
Any target occurrence remains inside [left,right).
values
[1,3,5,7,9]
target
7
left
0
right
5
bounds
"half-open"
phase
"search"
Discard the too-small prefix through mid.
Sorted order proves the discarded side cannot contain a target match. The interval strictly shrinks.
values
[1,3,5,7,9]
target
7
left
3
right
5
bounds
"half-open"
phase
"search"
before
[0,5]
mid
2
probeValue
5
found
false
Retain the eligible midpoint on the right boundary.
Sorted order proves the discarded side cannot contain a target match. The interval strictly shrinks.
values
[1,3,5,7,9]
target
7
left
3
right
4
bounds
"half-open"
phase
"search"
before
[3,5]
mid
4
probeValue
9
found
false
Return an equality witness; duplicates need not return their first index.
The probed original index contains target, satisfying the any-match contract.
values
[1,3,5,7,9]
target
7
left
3
right
4
bounds
"half-open"
phase
"search"
before
[3,4]
mid
3
probeValue
7
found
true
Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
result
3

Duplicate equality permits any matching index

Input: {"nums":[2,2,2,2],"target":2} · Returned index: 2

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

Any target occurrence remains inside [left,right).

Exact lookup — retained element interval

Candidate element interval: [0, 4). Phase: search. Target: 2.

index 02retained element
index 12retained element
index 22retained element
index 32retained element

Highlight marks the last probed element, which may have just been discarded. Only indices inside the retained interval remain candidates unless a match has already been found.

State after this step
Variable	Value
values	`[2,2,2,2]`
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 search(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) return mid;
10             if (nums[mid] < target) left = mid + 1;
11             else right = mid;
12         }
13         return -1;
14     }
15     public static int baseline(int[] nums, int target) {
16         Objects.requireNonNull(nums, "nums");
17         for (int i = 0; i < nums.length; i++) if (nums[i] == target) return i;
18         return -1;
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.
Any target occurrence remains inside [left,right).
values
[2,2,2,2]
target
2
left
0
right
4
bounds
"half-open"
phase
"search"
Return an equality witness; duplicates need not return their first index.
The probed original index contains target, satisfying the any-match contract.
values
[2,2,2,2]
target
2
left
0
right
4
bounds
"half-open"
phase
"search"
before
[0,4]
mid
2
probeValue
2
found
true
Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
result
2

Empty lookup

Input: {"nums":[],"target":1} · Returned index: -1

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

Any target occurrence remains inside [left,right).

Exact lookup — retained element interval

Candidate element interval: [0, 0). Phase: search. Target: 1.

Empty array — no probeable elements.

Highlight marks the last probed element, which may have just been discarded. Only indices inside the retained interval remain candidates unless a match has already been found.

State after this step
Variable	Value
values	`[]`
target	`1`
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 search(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) return mid;
10             if (nums[mid] < target) left = mid + 1;
11             else right = mid;
12         }
13         return -1;
14     }
15     public static int baseline(int[] nums, int target) {
16         Objects.requireNonNull(nums, "nums");
17         for (int i = 0; i < nums.length; i++) if (nums[i] == target) return i;
18         return -1;
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.
Any target occurrence remains inside [left,right).
values
[]
target
1
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
-1

Test the contract

Input: []
Output: −1
Empty search.
Input: [4], target=4 or 3
Output: 0 or −1
Singleton match and absence.
Input: [1,2,3], target=1 or 3
Output: 0 or 2
Both endpoints.
Input: [2,2,2], target=2
Output: Any valid matching index
Duplicate-aware oracle.
Input: [MIN,0,MAX], target=MAX
Output: 2
No target arithmetic overflow.

Common mistakes and counterexamples

Require the baseline’s exact duplicate index

Counterexample: All-equal [2,2,2,2] yields optimized index 2 and baseline index 0; both satisfy the API.

Check presence and a valid equal-valued witness, not identical outputs.

Set left=mid after a smaller value

Counterexample: With two candidates, mid can equal left and the interval stops shrinking.

Exclude the already compared index with left=mid+1.

Use right=n−1 with the half-open loop

Counterexample: A one-element array starts [0,0) and never checks its element.

Keep initialization, loop guard, and updates from one interval convention.

Infer an insertion point from −1

Counterexample: Absence is represented only by −1 here, not a transformed insertion boundary.

Use DSA-060 when the boundary itself is required.

Follow-ups

Return the first occurrence.

Search for the first value >=target, then validate equality. Equality keeps the midpoint as a candidate rather than returning it.

Count occurrences.

Subtract lower bound from upper bound. Searching target+1 to emulate upper bound is unsafe for Integer.MAX_VALUE.

Search objects using a comparator.

Require the same total ordering used to sort the collection. Comparator zero defines a match, which may differ from object identity or equals; do not subtract integer keys.

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 · 123/20,000 characters

Self-review

I can state exactly which indices remain possible.Every nonreturn iteration strictly shrinks my interval.My tests accept every valid duplicate witness and verify input preservation.

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.