How it works
A lower-bound search finds the first element not less than a target in a sorted array. It answers more than a yes-or-no membership question: the returned position is also where a new target could be inserted while preserving order. Repeated targets resolve to the first matching position.
The half-open search interval is [low, high). high starts at Length and is excluded from direct indexing. For target three, the answer is index one, before the repeated threes. For target five, the answer is three, before seven. For target nine, the answer is four, just after the array's final element.
Each comparison discards part of the candidate interval. If the middle value is too small, every earlier position through middle is too small as well. Otherwise the answer is at middle or earlier, so high becomes middle. The interval shrinks until low and high meet at the boundary.
Do not index the returned position without checking whether it equals Length. An insertion position at the end is a successful search outcome, not an exception-worthy missing array slot. To test membership, require index < Length and compare the element with the target after the boundary search finishes.
Practice with an empty array, all values equal, a target smaller than every element, and a target equal to the last value. Write down low and high at each iteration for one case. The midpoint formula avoids adding two potentially large indices directly, while preserving the intended midpoint.
Finally, implement an upper-bound variant that finds the first element greater than the target. Compare its result with lower bound to count duplicate occurrences. Both algorithms depend on the same sorted-order precondition; their difference is a precise comparison boundary that should be captured in tests rather than hidden in a vaguely named search helper.
A working example
using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;
using System.Text.Json;
using System.Text.Json.Serialization;
using System.Threading;
using System.Threading.Tasks;
using System.Runtime.CompilerServices;
int[] values = { 1, 3, 3, 7 };
Console.WriteLine(LowerBound(values, 3));
Console.WriteLine(LowerBound(values, 5));
Console.WriteLine(LowerBound(values, 9));
static int LowerBound(int[] values, int target) {
int low = 0, high = values.Length;
while (low < high) {
int middle = low + (high - low) / 2;
if (values[middle] < target) low = middle + 1;
else high = middle;
}
return low;
}
Expected output
1 3 4
The answer may equal Length, which is a valid insertion position but not a readable index.