This content originally appeared on DEV Community and was authored by Matteo
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
We are not searching for a number inside an array. We are searching for the minimum feasible capacity that meets a condition.
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: 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
Example: 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
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.
This content originally appeared on DEV Community and was authored by Matteo
Matteo | Sciencx (2025-11-10T20:41:23+00:00) Searching Algorithms Part 1: Binary Search and the Art of Cutting the Search Space. Retrieved from https://www.scien.cx/2025/11/10/searching-algorithms-part-1-binary-search-and-the-art-of-cutting-the-search-space/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.