Predicate Function

Function that returns either true or false

example

Monotonic Predicate Function

A monotonic predicate function is a function that returns true or false, where the result changes at most once as x increases.

Binary Search Monotonic Predicate Function

Define valid range of x minimum possible value of x => low maximum possible value of x => high

in range [low,high] function f(x) is Monotonic Predicate Function

Define ans to store the possible answer.

mid=low+(high-low)/2

if f(mid)=false means mid<A so update low=mid+1

if f(mid)=true means mid>=A

here mid is also possible answer so update ans=mid and high=mid-1

Final code templete

int low = 1;
int high = 1e9+7; //suppose [1,1e9+7] is valid range
int ans = -1; //No answer found yet

while(low <= high){
     int mid = low + (high - low) / 2;
     if(f(mid)){ //define f function also
          ans = mid;
          high = mid - 1;
     }
     else 
          low = mid + 1;
}
cout << ans << "\n";

Happy Coding!!!