Course contentsShow
← Computer Science
Lesson 810 of 2,87219. Searching and SelectionFree lesson

Lower Bound Search

Find the first position where a value could be inserted while maintaining sorted order.

Lower Bound Search

You'll learn how to find the leftmost valid insertion point in a sorted array.

What Is Lower Bound Search?

Lower bound search is a variant of binary search that finds the first position where a value could be inserted while keeping the array sorted. Unlike standard binary search, which only tells you if an element exists, lower bound answers: "Where does this value belong?"

Think of it like finding where to insert a new card into an already-sorted hand of playing cards—you want the leftmost spot where it fits.

How It Differs from Standard Binary Search

Standard binary search stops when it finds a match (or reports "not found"). Lower bound search continues until it identifies the first position where array[position] >= target. This means:

  • If the target exists, you get its first occurrence
  • If the target doesn't exist, you get where it would be inserted

The Core Idea

Use binary search, but instead of returning on equality, keep narrowing toward the left. When you find a candidate position, check if you can move further left while still maintaining the "greater than or equal" property.

The algorithm adjusts the search space:

  • If array[mid] < target, search right (move left = mid + 1)
  • If array[mid] >= target, this could be the answer, but keep searching left (move right = mid)

Eventually, left converges to the lower bound position.

Why It Matters

Lower bound is essential for:

  • Finding the first occurrence of duplicates
  • Implementing range queries (find all elements in [a, b])
  • Insertion into sorted collections
  • Many library functions (C++'s lower_bound, Python's bisect_left)

Key Takeaway: Lower bound search finds the leftmost insertion position for a target value in O(log n) time, returning where the value is or should be.