First True: Predicate Binary Search
Search a monotonic yes/no boundary.
First True: Predicate Binary Search is a free Coding Interview Prep lesson on CoddyKit. This is lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, and your progress syncs across the web and the CoddyKit app. The Coding Interview Prep course includes 4 lessons in total.
Search a Yes/No Boundary
Many problems hide a monotonic predicate: false, false, then true forever. Binary search can find that first true without a sorted array.
# FFFFTTTT -> find first TWhat Monotonic Means
A predicate is monotonic when once it turns true it stays true. That single property is what lets you binary-search the boundary.
def ok(x):
return x * x >= targetFrame the Answer Space
Pick a range that surely contains the boundary. Set low to the smallest candidate and high to a value where ok is certainly true.
low, high = 0, 10**9Test the Middle
Take mid and call ok(mid). The boolean result tells you which half to keep, exactly like comparing a value in plain binary search.
mid = (low + high) // 2
if ok(mid):
...True Means Maybe Smaller
If ok(mid) is true, mid is a valid answer but a smaller one might also work. Keep mid by setting high = mid, not mid - 1.
if ok(mid):
high = midFalse Means Go Higher
If ok(mid) is false, the boundary lies above mid. Discard mid and everything below it with low = mid + 1.
else:
low = mid + 1Loop While Low Is Below High
Use while low < high, not less-than-or-equal. The two pointers converge onto the first true index and then the loop stops.
while low < high:
mid = (low + high) // 2The Answer Is Low
When the loop ends, low equals high and both point at the first true value. Return low as the boundary you were hunting.
return low # first x where ok(x)Why high = mid Works
Because mid can be the answer, you must not skip it. Using high = mid keeps it in range while still shrinking, guaranteeing progress.
high = mid # mid stays a candidateInteger Square Root Example
To find the largest x with x*x at most n, search the first true of x*x > n, then step back one. The pattern reuses itself.
def ok(x):
return x * x > n
# answer is found_index - 1One Template, Many Problems
This first-true template solves countless tasks: minimum feasible value, leftmost index, smallest capacity. Learn it once, reuse it everywhere.
# low<high, ok->high=mid, else low=mid+1Quick Check
Pin down the move that keeps the candidate alive.
Recap: First True Found
You can now turn a problem into a monotonic predicate and binary-search the boundary. high = mid plus while low < high is the safe pattern. 🧭
Learn Coding Interview Prep with an AI tutor — free
Write and run real code in your browser, get instant help from a 24/7 AI tutor, and pick up where you left off on the web or in the app.
- Courses
- 90
- Lessons
- 360
Frequently Asked Questions
Is the “First True: Predicate Binary Search” lesson free?
Yes — the full text of “First True: Predicate Binary Search” is free to read here on the web. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO. The Coding Interview Prep course includes 4 lessons in total.
What will I learn in “First True: Predicate Binary Search”?
Search a monotonic yes/no boundary. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners, so you can start here or from the beginning and move at your own pace. This is lesson 3 of 4.
How long does the “First True: Predicate Binary Search” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Classic Binary Search Without Bugs
- bisect_left and bisect_right
- First True: Predicate Binary Search
- Binary Search on the Answer