| name | algo-linear-binary-search |
| description | Implement Python linear/binary search: first/last occurrence, lower_bound/upper_bound (bisect), rotated-sorted-array search. Use when finding an index, searching sorted data, counting duplicates, or finding an insertion point. |
| tool_type | python |
| primary_tool | Python |
Linear and Binary Search
When to Use
- Finding the index of a value in a list/array (
find X in arr, "search for element").
- Data is unsorted, small (< ~20 elements), a linked list, or searched only once → linear search.
- Data is sorted and searched repeatedly, or large → binary search, O(log n).
- Need the first/last position of a duplicated value, a count of occurrences, or an insertion point (
bisect_left/bisect_right equivalents).
- Searching a sorted array that has been rotated (e.g., a circular buffer or a sorted log that wrapped around).
Version Compatibility
Pure Python stdlib — no external dependencies. Verified on Python ≥3.8 (uses typing.List/Optional; on 3.9+ you can use built-in list/None union syntax instead). bisect module used for cross-checking is stdlib in every Python 3 version.
Prerequisites
- No packages to install. Optional:
bisect (stdlib) to validate lower_bound/upper_bound against bisect_left/bisect_right.
- Concepts: array indexing,
O(n)/O(log n) complexity basics.
Complexity
| Linear | Binary |
|---|
| Best | O(1) | O(1) |
| Average/Worst | O(n) | O(log n) |
| Space (iterative) | O(1) | O(1) |
| Space (recursive) | O(1) | O(log n) — call stack |
| Prerequisite | None | Sorted array |
Goal: find the index of target in an unsorted or small collection.
Approach: scan left to right, return on first match, -1 if exhausted.
from typing import List
def linear_search(arr: List[int], target: int) -> int:
"""Search for target in arr using linear search.
Time: O(n), Space: O(1). Works on unsorted data.
"""
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
Goal: find target in a sorted array in O(log n).
Approach: repeatedly halve the search window [left, right]; compare arr[mid] to target to decide which half to keep.
from typing import List, Optional
def binary_search_iterative(arr: List[int], target: int) -> int:
"""Iterative binary search on a sorted array.
Time: O(log n), Space: O(1).
"""
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
def binary_search_recursive(
arr: List[int], target: int, left: Optional[int] = None, right: Optional[int] = None
) -> int:
"""Recursive binary search. O(log n) time, O(log n) stack space."""
if left is None:
left = 0
if right is None:
right = len(arr) - 1
if left > right:
return -1
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
Goal: with duplicates present, find the first/last occurrence, count them, or find an insertion point (bisect_left/bisect_right equivalents).
Approach: on a match, don't stop — keep narrowing toward the boundary you want (left for "first", right for "last"); for bounds, use a half-open [left, right) window.
from typing import List
def find_first_occurrence(arr: List[int], target: int) -> int:
"""Leftmost index of target in a sorted array with duplicates, or -1."""
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
result = mid
right = mid - 1
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
def find_last_occurrence(arr: List[int], target: int) -> int:
"""Rightmost index of target in a sorted array with duplicates, or -1."""
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
result = mid
left = mid + 1
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
def count_occurrences(arr: List[int], target: int) -> int:
"""Count occurrences of target via two O(log n) binary searches."""
first = find_first_occurrence(arr, target)
if first == -1:
return 0
return find_last_occurrence(arr, target) - first + 1
def lower_bound(arr: List[int], target: int) -> int:
"""First index with arr[i] >= target (equivalent to bisect.bisect_left)."""
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left
def upper_bound(arr: List[int], target: int) -> int:
"""First index with arr[i] > target (equivalent to bisect.bisect_right)."""
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] <= target:
left = mid + 1
else:
right = mid
return left
Goal: search a sorted array that was rotated at an unknown pivot (e.g. [4,5,6,7,0,1,2], originally [0,1,2,4,5,6,7]).
Approach: one half of [left, mid, right] is always properly sorted; check which half is sorted, then check if target falls in that half's range to decide where to recurse.
from typing import List
def search_rotated_array(arr: List[int], target: int) -> int:
"""Search a rotated sorted array (no duplicates) in O(log n)."""
if not arr:
return -1
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
if arr[left] <= arr[mid]:
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
else:
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return -1
def _demo() -> None:
"""Self-check: run against Python's bisect and known test cases."""
import bisect
sorted_dups = [1, 3, 5, 5, 5, 7, 9]
assert find_first_occurrence(sorted_dups, 5) == 2
assert find_last_occurrence(sorted_dups, 5) == 4
assert count_occurrences(sorted_dups, 5) == 3
assert count_occurrences(sorted_dups, 4) == 0
for target in [0, 1, 4, 5, 6, 9, 10]:
assert lower_bound(sorted_dups, target) == bisect.bisect_left(sorted_dups, target)
assert upper_bound(sorted_dups, target) == bisect.bisect_right(sorted_dups, target)
assert binary_search_iterative(list(range(1, 10)), 7) == 6
assert binary_search_iterative([], 5) == -1
assert binary_search_recursive(list(range(1, 10)), 7) == 6
rotated = [4, 5, 6, 7, 0, 1, 2]
assert search_rotated_array(rotated, 0) == 4
assert search_rotated_array(rotated, 6) == 2
assert search_rotated_array(rotated, 3) == -1
assert search_rotated_array([1], 1) == 0
assert search_rotated_array([2, 1], 1) == 1
print("all checks passed")
if __name__ == "__main__":
_demo()
Pitfalls
- Integer overflow in
(left + right) // 2 — safe in Python (arbitrary precision), but use left + (right - left) // 2 if porting to C/Java.
- Off-by-one errors:
left <= right (inclusive bounds, classic search) vs left < right (half-open bounds, used for lower_bound/upper_bound) require different loop conditions and updates — mixing them causes infinite loops or missed elements.
- Binary search on unsorted data silently returns a wrong index — no exception is raised.
find_first_occurrence/find_last_occurrence must not return immediately on a match — stopping early only finds a match, not the boundary one.- Rotated-array search: don't assume the left half is unsorted just because
arr[left] > arr[mid] — that only tells you the right half is the sorted one; check both cases explicitly.
- For real code, prefer stdlib
bisect.bisect_left/bisect.bisect_right over hand-rolled lower_bound/upper_bound — they're implemented in C and battle-tested.
See Also
- algo-sorting-fundamentals (data usually needs sorting before binary search applies)
- algo-complexity-analysis
- algo-tree-structures (binary search trees generalize binary search to dynamic data)
