1. Introduction: The Hook of Today
If the two-pointer technique taught us how to traverse data efficiently, searching algorithms teach us how to find efficiently.
When you need to locate something in a sorted structure, your first instinct might be to scan linearly. But that wastes information. If the data is sorted, we can always ask smarter questions than “is it here?”.
Think of it as playing a guessing game with someone who says higher or lower. Instead of checking every number one by one, you can halve the range of possibilities each time. That is the power of binary search.
Today we begin our three-part exploration of searching algorithms. We start from the simplest form of reasoning on ordered data, build up to flexible patterns like search on answer, and finish with mountain arrays and bitonic sequences.
2. The Naive Idea
Before diving into binary search, it helps to remember what the linear approach does.
A linear search scans each element until it finds the target or reaches the end.
def linear_search(nums, target):
for i, x in enumerate(nums):
if x == target:
return i
return -1
It is simple, clear, and terrible for large inputs.
Complexity
Time: O(N)
Space: O(1)
This brute-force approach ignores a crucial fact: in sorted data, every comparison tells you whether you can discard half of the array. That means you can cut your work in half each time instead of checking everything.
3. Core Concept: Binary Search
Binary search relies on the idea of halving the search interval until the target is found. It is one of the most fundamental algorithmic patterns in computer science.
Example: Classic Binary Search
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
How It Works
- Choose the middle element.
- Compare it to the target.
- Depending on the result, discard half of the array.
- Repeat until the interval becomes empty.
Complexity
Time: O(log N)
Space: O(1)
Binary search is not limited to finding a specific value. Once you understand how to manipulate the condition, you can adapt it to a wide range of optimization and boundary problems.
4. Beyond Finding a Value: Searching on a Condition
Many problems ask for the smallest or largest value that satisfies a condition rather than an exact match. This is called searching on the answer.
The idea is to perform binary search over the solution space rather than over the array itself.
Example: Minimum Capacity to Ship Packages Within D Days
def ship_within_days(weights, days):
left, right = max(weights), sum(weights)
while left < right:
mid = (left + right) // 2
if can_ship(weights, days, mid):
right = mid
else:
left = mid + 1
return left
def can_ship(weights, days, capacity):
days_needed = 1
current = 0
for w in weights:
if current + w > capacity:
days_needed += 1
current = 0
current += w
return days_needed <= days
How It Works
We are not searching for a number inside an array. We are searching for the minimum feasible capacity that meets a condition.
- The smallest possible capacity (left) must be at least the heaviest package, because we cannot split a single item.
- The largest possible capacity (right) is the sum of all packages, meaning we could ship everything in one day.
- We test a middle value (mid) as a candidate capacity.
- The helper function can_ship simulates the loading process:
- It fills the current ship until adding another package would exceed the capacity.
- When that happens, it increments days_needed and resets the load counter.
- In the end, it checks whether the number of days used is less than or equal to the limit.
If we can successfully ship within the allowed number of days, the capacity might be reduced further, so we move right down. Otherwise, we increase left to test larger capacities.
Complexity
Time: O(N log S), where S is the numeric search range.
Space: O(1)
5. Lower Bound and Upper Bound
Binary search can also locate positions relative to a target even if the target itself does not exist.
These are known as lower bound and upper bound searches.
- Lower bound: first index where the element is greater than or equal to the target.
- Upper bound: first index where the element is strictly greater than the target.
def lower_bound(arr, target):
low, high = 0, len(arr)
while low < high:
mid = (low+high) // 2
if arr[mid] < target:
low = mid+1
else:
high = mid
return low
def upper_bound(arr, target):
low, high = 0, len(arr)
while low < high:
mid = (low+high) // 2
if arr[mid] <= target:
low = mid+1
else:
high = mid
return low
Why It Matters
These patterns appear everywhere:
- Finding insertion positions
- Counting elements less than a value
- Solving “k-th smallest” problems
- Handling duplicates in sorted arrays
6. Bitonic and Rotated Arrays
Some problems involve arrays that are almost sorted, such as rotated or bitonic arrays. Binary search still works but requires conditional logic.
Example 1: Search in Rotated Sorted Array
def search_rotated(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
Key Idea
- At every step, at least one side of the array is sorted.
- We first check which side is sorted by comparing nums[left] and nums[mid].
- If the target lies within that sorted range, we restrict our search to that side by moving the appropriate pointer. Otherwise, we move to the other side.
This approach keeps halving the search space even when the array has been rotated.
Example 2: Find the Peak in a Bitonic Array
A bitonic array increases and then decreases. The peak can be found by comparing neighbors.
def find_peak(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] < nums[mid + 1]:
left = mid + 1
else:
right = mid
return left
Key Idea
We compare the middle element to its next neighbor:
- If nums[mid] is smaller than nums[mid + 1], we are on the increasing slope, so the peak lies to the right.
- If nums[mid] is greater than or equal to nums[mid + 1], we are on the decreasing slope, so the peak lies to the left or at mid.
This continues until left and right meet at the highest point.
Complexity
Time: O(log N)
Space: O(1)
7. Quick Comprehension Check
Question
You are given an ascending array of positive integers and a value x. How would you find the smallest number in the array that is greater than or equal to x?
Answer
Use a lower-bound binary search to find the first index where nums[mid] >= x.
8. Final Summary and Review
Binary search is not only about finding numbers. It is about thinking in terms of ranges and conditions. Once you understand that every comparison halves your possibilities, you can apply the same logic to scheduling, geometry, optimization, and even model tuning.
9. Hook for Tomorrow
Today we saw how binary search and its variations help us explore numeric and ordered data.
Next, we move to searching in strings. You will learn how algorithms such as Z, KMP, and Rabin–Karp detect patterns efficiently, and how they can combine with binary search to find repeated substrings or the longest common prefix.
In Part 2, we will uncover how strings can be searched not by brute force, but through clever preprocessing and pattern recognition.
Top comments (0)