Understanding the maximum predicate search pattern
There are many problems where we may not be given a sorted sequence, but an ordered search space where every input may either be a valid solution or not. The maximum predicate search algorithm generalizes the binary search algorithm to find the maximum value that satisfies a predicate function. It is the natural counterpart of the minimum predicate pattern and can solve a wide variety of optimization problems.
The maximum predicate search is the technique to find the maximum value in the search space after which the predicate flips.
In this lesson, we will learn more about using the maximum predicate search algorithm to solve problems where we need to find the maximum predicate, and how to identify a problem as a maximum predicate search pattern problem.
The maximum predicate search problem
Consider we have a search space defined by an ordered set S where values are sorted in non-decreasing order, and a predicate function p that takes as input values from the set S and returns either true or false. The results of the predicate function p are monotonic over the search space and flip only once from true to false or from false to true.
A monotonic sequence of true and false, starting from true, that flips once over a sorted space.
Liking the course? Check our discounted plans to continue learning.