15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Topic 10 of 12 in the free DSA Basics course · 6 lessons
Choose and implement a search strategy based on the structure of the data:
State the input structure and maintain a rule about which answers remain possible. These searches read the input; they do not mutate the array or numeric range.
There are no required prior lessons.
You should be comfortable with:
<, >, and ==.Start with the sorted array A = [1, 4, 6, 9, 12] and target 9.
For Linear Search, inspect values from left to right:
0: 1 is not 9.1: 4 is not 9.2: 6 is not 9.3: 9 matches, so return 3.For Binary Search Fundamentals, use the fact that A is sorted:
[0, 4].2, whose value is 6.6 < 9, neither index 0, 1, nor 2 can contain 9. Keep [3, 4].3, whose value is 9.3.Both searches return 3. Linear search requires no ordering assumption. Binary search requires sorted order, which proves that an entire half cannot contain the target.
If the array were [4, 1, 9, 6, 12], ordinary binary search would be invalid. Use linear search unless you can establish a different structure, such as a rotated sorted array.
Linear Search establishes the baseline scan and the meaning of a found result versus an absent result. It works when the data has no ordering.
Binary Search Fundamentals introduces a candidate interval on a sorted array. The sorted-array precondition lets one comparison discard half of that interval.
Binary Search Variants reuses the same interval reasoning when an exact match is insufficient. Duplicates require a boundary rule, such as “the first index whose value is at least the target.”
Search in Rotated Arrays builds on ordinary binary search. Identify the sorted half, then determine whether the target can lie there.
Search Space Reduction moves binary search beyond array lookup. Search an ordered integer domain for the first value where a monotone predicate changes from false to true.
Ternary Search Basics uses another interval-reduction method. Its precondition differs: the values must form a strictly unimodal discrete sequence, allowing you to discard the side that cannot contain the maximum.
The lesson order moves from the least restrictive search to increasingly specialized structures.
Linear Search needs only a sequence of values. It may inspect every element, so its worst-case time grows linearly with the array size.
Binary Search Fundamentals requires sorted order. At each midpoint, comparison with the target identifies an impossible half. Each iteration cuts the remaining interval by a constant factor, so the number of iterations is logarithmic.
Binary Search Variants keeps the sorted-array requirement and changes the question. The question can be:
target?target?Each question depends on an invariant: a statement that remains true after every boundary update.
Search in Rotated Arrays replaces global sortedness with a precise structure: a strictly increasing array rotated once, with distinct values. In each interval, at least one half is sorted. That property determines whether to keep the sorted half or the other half.
Search Space Reduction replaces array values with a monotone Boolean predicate. For example, suppose canFinish(days) is false for too few days and true once enough days are available. Binary search finds the smallest feasible number of days even when no array contains that answer.
Ternary Search Basics applies only to a strictly unimodal sequence that rises to one maximum and then falls. Comparing two interior values identifies an outer portion that cannot contain the maximum. The interval shrinks to roughly two thirds each iteration, which is still logarithmic.
Before choosing an algorithm, classify the search space:
Implement Linear Search for present and absent targets on both sorted and unsorted arrays. Record every comparison for a small input.
Implement Binary Search Fundamentals with inclusive low and high boundaries. Trace successful searches, absent targets smaller than every value, and absent targets larger than every value.
Use Binary Search Variants on an array with duplicates, such as [1, 4, 4, 4, 9]. Find the first 4, last 4, and insertion index for 6.
Practice Search in Rotated Arrays with a distinct-value input such as [9, 12, 1, 4, 6]. At each step, state which half is sorted and why the target is kept or discarded.
Practice Search Space Reduction with a threshold problem over integers. Define a predicate such as “is this capacity sufficient?” and find the smallest capacity for which it becomes true.
Practice Ternary Search Basics on a strictly unimodal sequence such as [2, 5, 8, 11, 7, 3]. Track both split indices and explain why the discarded region cannot contain the maximum.