The process of locating a specific item or value within a collection of data using a systematic strategy. The two fundamental approaches are linear search (check every element one by one) and binary search (repeatedly halve the search space in sorted data).
Looking for a book on a shelf, a name in a list, a file on your computer.
Showing a random 20 of 50 problems.
Example 1
medium
Use linear search to find the value 7 in the list [3, 9, 7, 1, 5]. How many comparisons are needed?Linear search for 7: comparisons at indices 0, 1, then match at index 2
Example 2
medium
Binary search a sorted ascending list. The middle is smaller than the target. Which half do you keep?
Example 3
medium
A sorted array has 1,048,576 elements. Worst-case binary search comparisons?
Example 4
easy
Linear search on n items has what worst-case number of comparisons?
Example 5
medium
Linear search for 6 in `[1, 2, 6, 6, 6]` returning the first match index. What is the result?Linear search for first 6: compare 1 (no), compare 2 (no), compare 6 at index 2 (match) — return index 2
Example 6
easy
A correct search function returns what when the target is not found?
Example 7
medium
Can binary search be used on the unsorted list [8, 2, 5, 1, 9]? Why or why not?Unsorted list — binary search cannot be applied correctly
Example 8
medium
Linear search a 6-element list for a value that is absent. How many comparisons are made?
Example 9
medium
You sort an unsorted list of n items once (cost ∼nlogn) and then search it k times with binary search (each ∼logn). When is this beat by k linear searches?
Example 10
medium
Worst case, how many comparisons does binary search need on 1000 sorted items?
Example 11
easy
Linear search for 9 in `[2, 4, 9, 7, 1]`. How many comparisons until found?Linear search for 9: compare 2 (no), compare 4 (no), compare 9 (match) — 3 comparisons
Example 12
challenge
You must search an UNSORTED array of n once for one value. Is it worth sorting first (O(nlogn)) to use binary search (O(logn))?
Example 13
medium
A phone book is sorted by name. To find 'Smith', which search is far more efficient than scanning page by page?
Example 14
medium
Linear search for 7 in `[3, 7, 7, 7]`, returning the LAST occurrence's index. What does it return?Linear search for last 7: scan all elements, keep updating last-match index; return index 3
Example 15
hard
A buggy binary search computes `mid = (low + high) // 2` but never updates `low = mid + 1` or `high = mid - 1`. What failure occurs?
Example 16
easy
For binary search, worst-case comparisons on n items grow like which function?
Example 17
medium
Binary search needs the data sorted. If you receive unsorted data and must search it many times, what is the right preprocessing step?
Example 18
easy
Binary search a sorted array. The middle element equals the target. What happens?
Example 19
hard
A sorted list has 128 elements. In the worst case, about how many comparisons does binary search need, and how does that compare with linear search?
Example 20
medium
Binary search in sorted `[2,5,8,12,16,23,38,56,72,91]` (10 items) for 23. First midpoint is index 4 (value 16). Which half is searched next?Binary search for 23: first midpoint is index 4 (value 16); 23 > 16 so search the right half