What you will learn
The half-open range invariant that makes binary search correct on the first try
Lower bound and upper bound: finding the first index where a condition becomes true
2D binary search on a strictly sorted matrix and staircase search on a row-and-column sorted matrix
Finding the pivot and searching in a sorted rotated array in O(log N)
Minimum and maximum predicate search to binary search any monotonic predicate
How to spot a binary-search-on-answer problem hidden behind an optimisation question
Why this course
Most engineers can recite the binary search recipe and still spend half an hour fixing off-by-one bugs the first time they have to write it from scratch in an interview. The recipe falls apart the moment the input has duplicates, or the array is rotated, or the search space isn't an array at all.
This course rebuilds searching from the search-space invariant up. You see why binary search works, how the lower-bound and upper-bound variants fix the duplicate case, how to binary-search a 2D matrix or a rotated array, and how the same halving idea generalises to any monotonic predicate over an integer range.
Requirements
The course assumes you can read code in any mainstream language and you have seen an array before. No prior searching experience is needed.
- Comfort writing loops, conditionals, and functions in at least one language.
- Familiarity with Big-O notation, especially O(log N) versus O(N).
- Basic array operations: indexing, length, and iteration.
Overview
Searching is the operation every other algorithm leans on. A hash table is a search structure. A binary search tree is a search structure. The binary search step inside merge sort, the lookup inside a Dijkstra priority queue, the range query in a database index, the autocomplete dropdown, all of them are some flavour of searching a sorted or partially-sorted space. Knowing how the underlying search algorithm halves the space is what turns a one-second query into a one-millisecond one.
Representation of searching
This course covers both halves of the problem: how binary search and its variants actually work on real inputs, and how to recognise which variant a new problem reduces to.
Fundamentals
The course opens with binary search on a sorted array. You see how the low and high indices define a search range, why mid = low + (high - low) / 2 avoids the integer-overflow bug that bites engineers in C++ and Java, and why the loop terminates exactly when low exceeds high. This first pass leaves you with binary search in O(log N) time and O(1) space, plus a clean mental model for the off-by-one questions that follow.
From there the course handles the cases binary search alone cannot solve. Lower bound finds the first index where arr[i] >= target, the version you want on a sorted array with duplicates. Upper bound finds the first index where arr[i] > target, the version you want for counting occurrences and ceiling-style queries. Both variants use a half-open range [low, high) instead of the inclusive range the classic algorithm uses, and the course makes that distinction concrete by showing where each one breaks if you mix them up.
The fundamentals close with the harder geometries. A strictly sorted 2D matrix can be searched in O(log(N * M)) by treating the matrix as a flattened 1D sequence with row = mid / M and col = mid % M. A row-and-column sorted matrix breaks that global ordering, so staircase search walks from the top-right corner instead, running in O(N + M). A sorted array rotated an unknown number of times still admits O(log N) search by checking which half between low, mid, and high is sorted and discarding the rest.
Problem solving
After the fundamentals, the course turns to patterns. Binary search is not one algorithm but a family of five, and most search problems you will see in an interview reduce to one of them. Once you can recognise which template the problem fits, the implementation is largely mechanical.
arr[i] >= target on a sorted array using a half-open range, useful for insertion points and duplicate-aware queries in O(log N) time. Search Insert Position, First and Last Position, Closest Element, K Closest Elements.arr[i] > target on a sorted array, the variant you want for counting occurrences and ceiling-style lookups in O(log N) time. Limit Count, Positive Index, Ceiling Index, Breaking Index.C is the predicate cost. Punctual Arrival Speed, Penalty With Balls, Minimum Shipping Capacity, Trip Completion Frenzy.mid = low + (high - low + 1) / 2 to avoid infinite loops. Calculate Square Root, Build Staircase, K Ribbons, Equalise Water.Each pattern is taught in three layers. An Understanding lesson develops the technique on a problem where the pattern is obvious. An Identifying lesson teaches the signals that tell you a new problem fits the template, the same triggers an experienced engineer spots in seconds during a real interview. Four problems per pattern then drill progressively harder applications, ending in the predicate-search patterns where the search space is no longer an array but an abstract integer range. By the last lesson, "binary search on the answer" stops feeling like a trick and starts feeling like the obvious move.
How this course is different
Most binary-search material on the internet shows you the textbook three-branch version, then leaves you to discover the variants on your own through trial and error.
[low, mid, high] is always sorted.Who this course is for
The course suits anyone who needs binary search to stop being the algorithm they almost get right.
- New programmers who have seen binary search in a textbook but have never implemented it cleanly under time pressure.
- Self-taught and bootcamp graduates who can solve sorted-array problems but stall when the input is rotated or the target has duplicates.
- Working developers who use
bisect_left,lower_bound, orArrays.binarySearchfrom a standard library and want to understand what those functions actually return. - Engineers preparing for FAANG and Big Tech interviews where binary-search-on-answer and rotated-array questions show up across the onsite loop.
- Returning engineers who learned binary search years ago and want a refresher that covers the predicate-search generalisation.
- Anyone who has written
low <= highandlow < highinterchangeably without knowing which is correct, and wants to fix that.
Continue your DSA journey
Searching connects naturally to the data structures it operates on and the problems where binary search hides inside a larger algorithm.
- Array: Binary search lives on top of an array's contiguous memory and O(1) indexing. The two-pointer reduction pattern in the array course also assumes a sorted input, so the two courses reinforce each other.
- Hash table: Hashing is the alternative to searching when you need O(1) lookup instead of O(log N) and you don't need ordered access. Knowing both lets you pick the right tradeoff: hash for unordered membership, binary search for ranked queries and ceiling/floor lookups.
- Binary search tree: A BST is the dynamic version of a sorted array, supporting O(log N) search alongside insertion and deletion. Many BST operations mirror lower bound and upper bound on sorted arrays.
- Heap: Heaps and binary search both halve work using the structure of the input. Floyd's build-heap runs in O(N) by exploiting the same halving idea binary search uses on a sorted array, so the complexity intuition transfers.
- Sorting: Binary search needs a sorted input, so sorting is the prerequisite that unlocks everything in this course. Quickselect uses the same partition step as quicksort but with a binary-search-style elimination, and several predicate-search problems sort before they search.
- Dynamic programming: Several DP problems use binary search on the answer to compress a feasibility check into an optimisation, and longest-increasing-subsequence runs in O(N log N) by binary-searching a tails array.
Frequently asked questions
mid = low + (high - low) / 2 formula because the naive (low + high) / 2 overflows in C++ and Java but not in Python.for loop and read Big-O like O(N) and O(log N). Binary search itself is taught from scratch with the half-open range invariant developed step by step.< or <= in the loop condition.i where arr[i] >= target, so on a sorted array with duplicates it points at the first occurrence of the target (or the insertion point if the target is absent). Upper bound returns the first index i where arr[i] > target, so it points just past the last occurrence of the target. The count of a target in a sorted array is upper_bound(target) - lower_bound(target), which is why both variants exist in the C++ standard library and in Python's bisect module as bisect_left and bisect_right.