7.2 Lower Bound Searches

The most useful form of binary search is not exact lookup. It is lower bound.

Given a sorted sequence and a target value, a lower-bound search returns the first position whose value is greater than or equal to the target. This operation appears in databases, search engines, interval systems, scheduling software, order books, and indexing structures because it identifies where a value belongs, regardless of whether the value already exists.

Many algorithms that appear unrelated to binary search become simpler once they are reformulated as lower-bound problems.

Problem

You have a sorted array and need to find the first element that is greater than or equal to a target value.

For example:

Index:  0  1  2  3  4  5
Value:  2  4  4  4  7  9

For target 4, the answer is index 1.

For target 5, the answer is index 4.

For target 10, the answer is position 6, which represents insertion at the end of the array.

A linear scan works:

func LowerBoundLinear(nums []int, target int) int {
	for i, v := range nums {
		if v >= target {
			return i
		}
	}

	return len(nums)
}

This solution requires O(n) comparisons.

For large collections, a logarithmic solution is preferable.

Solution

Use binary search to locate the boundary between values smaller than the target and values greater than or equal to the target.

func LowerBound(nums []int, target int) int {
	lo, hi := 0, len(nums)

	for lo < hi {
		mid := lo + (hi-lo)/2

		if nums[mid] >= target {
			hi = mid
		} else {
			lo = mid + 1
		}
	}

	return lo
}

Example:

nums := []int{2, 4, 4, 4, 7, 9}

fmt.Println(LowerBound(nums, 4))
fmt.Println(LowerBound(nums, 5))
fmt.Println(LowerBound(nums, 10))

Output:

1
4
6

Understanding the Boundary

The key observation is that lower bound searches for a transition point.

Consider:

nums   = [2, 4, 4, 4, 7, 9]
target = 5

Evaluating the condition:

nums[i] >= 5

produces:

Index:      0     1     2     3     4     5
Condition:  F     F     F     F     T     T

The array itself is almost irrelevant. Binary search operates on the pattern:

False False False False True True

The objective is to locate the first true value.

Many binary search problems can be reduced to this exact form.

Finding an Insertion Position

Lower bound naturally solves insertion problems.

Suppose a sorted collection must remain ordered after inserting a new value.

[2, 4, 4, 4, 7, 9]

Insert:

Lower bound returns index 4.

The new array becomes:

[2, 4, 4, 4, 5, 7, 9]

The insertion position is found without scanning the collection.

This property is heavily used inside balanced trees, B-trees, skip lists, database indexes, and storage engines.

Finding the First Occurrence

A common interview question asks for the first occurrence of a value in a sorted array containing duplicates.

Many developers initially write:

func Search(nums []int, target int) int {
	lo, hi := 0, len(nums)-1

	for lo <= hi {
		mid := lo + (hi-lo)/2

		if nums[mid] == target {
			return mid
		}

		if nums[mid] < target {
			lo = mid + 1
		} else {
			hi = mid - 1
		}
	}

	return -1
}

This finds an occurrence.

It does not guarantee the first occurrence.

For:

[2, 4, 4, 4, 7, 9]

the returned index might be 1, 2, or 3.

Lower bound solves the problem directly.

func FirstOccurrence(nums []int, target int) int {
	pos := LowerBound(nums, target)

	if pos == len(nums) {
		return -1
	}

	if nums[pos] != target {
		return -1
	}

	return pos
}

The first matching element is returned automatically because lower bound searches for the leftmost valid position.

Counting Occurrences

Lower bound becomes even more useful when combined with upper bound.

Given:

[2, 4, 4, 4, 7, 9]

Lower bound of 4:

Upper bound of 4:

The count is:

4 - 1 = 3

Implementation:

count := UpperBound(nums, target) -
         LowerBound(nums, target)

This technique appears frequently in frequency queries, inverted indexes, search engines, and analytics systems.

Lower Bound on Structures

The concept extends beyond arrays.

Suppose employees are sorted by salary:

type Employee struct {
	Name   string
	Salary int
}

You want the first employee whose salary is at least $100,000.

func LowerBoundSalary(
	employees []Employee,
	target int,
) int {
	lo, hi := 0, len(employees)

	for lo < hi {
		mid := lo + (hi-lo)/2

		if employees[mid].Salary >= target {
			hi = mid
		} else {
			lo = mid + 1
		}
	}

	return lo
}

Binary search requires ordering, not primitive values.

Any sortable key can be searched.

Lower Bound on Time

Scheduling systems frequently search timestamps.

Given:

Find the first event at or after:

09:30

The answer is:

09:45

A lower-bound search identifies the next valid event in logarithmic time.

Calendar systems, message queues, storage engines, and financial exchanges use this pattern extensively.

Generic Lower Bound

A reusable implementation can operate on any monotone condition.

func LowerBoundGeneric(
	lo, hi int,
	ok func(int) bool,
) int {
	for lo < hi {
		mid := lo + (hi-lo)/2

		if ok(mid) {
			hi = mid
		} else {
			lo = mid + 1
		}
	}

	return lo
}

Usage:

result := LowerBoundGeneric(
	0,
	len(nums),
	func(i int) bool {
		return nums[i] >= target
	},
)

This abstraction reveals the true nature of lower bound. The algorithm does not care about arrays. It only searches for a boundary between false and true.

Complexity Analysis

Let n be the size of the search space.

Each iteration removes approximately half of the remaining candidates.

The search space evolves as:

n
n/2
n/4
n/8
...
1

The number of iterations is:

log₂(n)

Time complexity:

Operation	Complexity
Lower bound	O(log n)
Lookup after search	O(1)
Total	O(log n)

Space complexity:

Resource	Complexity
Extra memory	O(1)

Common Mistakes

Returning immediately when a matching value is found converts a lower-bound search into an ordinary binary search and loses the first-occurrence guarantee.

Using len(nums)-1 as the upper boundary while still applying half-open interval update rules often introduces off-by-one errors.

Reading nums[result] without verifying that result < len(nums) can cause out-of-range access when the target exceeds all values.

Treating lower bound as an exact-search algorithm often leads to incorrect handling of duplicates. Lower bound identifies a position. Whether the target actually exists requires a separate validation step.

Takeaway

Lower bound is the fundamental binary-search operation. Exact lookup, first occurrence, insertion position, frequency counting, interval searching, timestamp queries, and many ordered-data operations can be expressed as lower-bound problems. Once you learn to identify the boundary between values that fail a condition and values that satisfy it, binary search becomes a general boundary-finding technique rather than a simple array lookup algorithm.