### Predicate Function↵
↵
fFunction 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!!!↵
↵
↵
↵
↵
example↵
↵
↵
↵
↵
### 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!!!↵
↵
↵
