1. Exclusive right
right starts one past the last valid index.
let right = arr.lengthTyporithm · medium
Lower Bound / First Match Search
▷ Interactive algorithm lablower-bound-searchsearchsorted-arrayfirst-matchboundary-search
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Lower Bound / First Match Search
Search Algorithms
Lower Bound Search finds the first index where a sorted array value is greater than or equal to target.
Lower bound is a Binary Search variant for insertion points and first matches.
It uses a half-open range: left is inclusive, right is exclusive.
When arr[mid] is too small, move left past mid.
Otherwise keep mid because it might be the first valid answer.
The returned index can equal arr.length when all values are smaller than target.
Preparing algorithm lab…
01
Find first value >= target.
02
Use right = arr.length.
03
Loop while left < right.
04
Keep mid when it could be the answer.
05
Return an insertion index.
function lowerBound(arr, target) {
let left = 0;
let right = arr.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Narrow range
Keep narrowing until left is the first valid insertion point.
while (left < right)3. Middle index
Probe the middle of the current half-open range.
const mid = Math.floor((left + right) / 2)4. Too small
If mid is too small, the lower bound must be to the right.
arr[mid] < target5. Move left
Discard mid and everything before it.
left = mid + 16. Keep mid
mid could be the first value >= target, so keep it.
right = mid7. Return insertion point
left is the first index whose value is not smaller than target.
return leftA complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.