Understanding the minimum predicate search pattern
Binary search is a very powerful search technique to search for an item in a sorted sequence. However, at its core, it's a decision-making technique that exploits the ordered nature of a sequence. 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 minimum predicate search algorithm generalizes the binary search algorithm to find the minimum value that satisfies a predicate function.
The minimum predicate search is the technique to find the minimum value in the search space at which the predicate flips.
In this lesson, we will learn more about using the minimum predicate search algorithm to solve problems where we need to find the minimum predicate, and how to identify a problem as a minimum predicate search pattern problem.
The minimum 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 false, that flips once over a sorted space.
Liking the course? Check our discounted plans to continue learning.