Identifying the lower bound pattern
The lower bound algorithm is a very versatile algorithm that can solve a wide variety of search problems. It is especially useful on non-decreasing arrays where there are repetitions. In most cases, the lower bound algorithm solves subproblems within a larger, more complex problem to make the overall solution more efficient. These are generally easy or medium problems where we must apply the lower bound algorithm one or more times or leverage its constraints to our benefit.
Search for the first item greater than or equal to the given value in a sorted search space.
If the problem statement or its solution follows the generic template below, it can be solved by applying the lower bound algorithm.
Given a sorted search space and a target value, find the first item greater than or equal to the target value.
Example
Let's consider the following problem as an example to better understand how to identify and solve a problem using the lower bound algorithm.
Problem statement: Given an integer array `arr` that is sorted in non-decreasing order and an integer `target`, find and return the first and last positions of the target in the array. If the target doesn't exist, return `[-1, -1]` instead.
Liking the course? Check our discounted plans to continue learning.