Lower Bound and Upper Bound
Implement bisect_left and bisect_right from scratch, then apply them to find first and last positions of a target value.
Lower Bound and Upper Bound is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What Are Lower and Upper Bounds?
The lower bound of a target value in a sorted array is the index of the first element greater than or equal to the target (often called bisect_left). The upper bound is the index of the first element strictly greater than the target (bisect_right). Together they bracket every occurrence of the target and enable O(log n) range queries.
These two operations are the foundation of many interview problems: count occurrences, find range, insert position, and more.
arr = [1, 2, 2, 2, 3, 5]
# lower bound of 2 => index 1 (first element >= 2)
# upper bound of 2 => index 4 (first element > 2)
# occurrences of 2 => upper - lower = 4 - 1 = 3
print('lower bound of 2:', 1)
print('upper bound of 2:', 4)
print('count of 2:', 4 - 1)Implementing Lower Bound (bisect_left)
bisect_left(arr, x) returns the leftmost index i such that arr[i] >= x, or len(arr) if all elements are smaller. The implementation uses an exclusive upper boundary: hi = len(arr), loop condition lo < hi, and update hi = mid when arr[mid] >= x. This ensures the answer converges to the leftmost valid position.
def bisect_left(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < x:
lo = mid + 1
else:
hi = mid # arr[mid] >= x, so potential answer
return lo # lo == hi == insertion point
arr = [1, 2, 2, 2, 3, 5]
print(bisect_left(arr, 2)) # 1
print(bisect_left(arr, 0)) # 0 (before all)
print(bisect_left(arr, 6)) # 6 (after all)
print(bisect_left(arr, 3)) # 4Implementing Upper Bound (bisect_right)
bisect_right(arr, x) returns the leftmost index i such that arr[i] > x. Only one line differs from bisect_left: the condition changes from arr[mid] < x to arr[mid] <= x. When arr[mid] <= x, the answer is strictly to the right of mid, so we set lo = mid + 1; otherwise we narrow from the right.
def bisect_right(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= x:
lo = mid + 1 # arr[mid] <= x, so answer is strictly right
else:
hi = mid
return lo
arr = [1, 2, 2, 2, 3, 5]
print(bisect_right(arr, 2)) # 4
print(bisect_right(arr, 0)) # 0
print(bisect_right(arr, 5)) # 6
print(bisect_right(arr, 4)) # 5Count Occurrences with Both Bounds
To count occurrences of a target in a sorted array in O(log n), apply both bounds: count = bisect_right(arr, target) - bisect_left(arr, target). If the count is 0 the target is absent. This is significantly faster than a linear scan and is the standard approach for frequency queries on sorted data.
import bisect
def count_occurrences(arr, target):
left = bisect.bisect_left(arr, target)
right = bisect.bisect_right(arr, target)
return right - left
arr = [1, 2, 2, 2, 3, 3, 5]
print(count_occurrences(arr, 2)) # 3
print(count_occurrences(arr, 3)) # 2
print(count_occurrences(arr, 4)) # 0
print(count_occurrences(arr, 1)) # 1Find First and Last Position of Target
LeetCode 34 'Find First and Last Position of Element in Sorted Array' asks you to return [first_idx, last_idx] in O(log n). The first position is bisect_left(arr, target) — but only if arr[result] == target. The last position is bisect_right(arr, target) - 1. If either check fails, return [-1, -1].
import bisect
def search_range(nums, target):
left = bisect.bisect_left(nums, target)
if left == len(nums) or nums[left] != target:
return [-1, -1]
right = bisect.bisect_right(nums, target) - 1
return [left, right]
print(search_range([5,7,7,8,8,10], 8)) # [3, 4]
print(search_range([5,7,7,8,8,10], 6)) # [-1, -1]
print(search_range([], 0)) # [-1, -1]Insert Position (LeetCode 35)
LeetCode 35 'Search Insert Position' asks: where would the target be inserted to keep the array sorted? This is exactly bisect_left(arr, target). If the target exists, bisect_left returns its index. If it does not exist, bisect_left returns the index where it would be inserted. No special-casing required — the same function handles both situations.
import bisect
def searchInsert(nums, target):
return bisect.bisect_left(nums, target)
print(searchInsert([1,3,5,6], 5)) # 2 (exists at index 2)
print(searchInsert([1,3,5,6], 2)) # 1 (would insert between 1 and 3)
print(searchInsert([1,3,5,6], 7)) # 4 (would append at end)
print(searchInsert([1,3,5,6], 0)) # 0 (would prepend)The Difference Between bisect_left and bisect_right
When no duplicates exist, bisect_left and bisect_right return the same index. The difference only matters when the target appears multiple times. bisect_left points to the first copy; bisect_right points one past the last copy. Always choose based on whether you want to insert before existing copies (left) or after (right).
import bisect
arr = [1, 2, 2, 2, 3]
# Insert a new 2 before all existing 2s
print(bisect.bisect_left(arr, 2)) # 1
# Insert a new 2 after all existing 2s
print(bisect.bisect_right(arr, 2)) # 4
# For a value not in array, both give same insertion point
print(bisect.bisect_left(arr, 2.5)) # 4
print(bisect.bisect_right(arr, 2.5)) # 4Applying Bounds to Sorted Frequency Queries
When you need to answer many range-frequency queries on a sorted array efficiently, precompute the sorted array once and use bisect for each query. Each query answers 'how many elements lie in [lo, hi]?' in O(log n) rather than O(n). This pattern appears in problems about counting elements within a value range after sorting.
import bisect
def count_in_range(arr, lo, hi):
'''Count elements in arr with lo <= val <= hi. arr must be sorted.'''
left = bisect.bisect_left(arr, lo)
right = bisect.bisect_right(arr, hi)
return right - left
arr = sorted([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
print(arr) # [1,1,2,3,3,4,5,5,5,6,9]
print(count_in_range(arr, 3, 5)) # 6 (3,3,4,5,5,5)
print(count_in_range(arr, 1, 2)) # 3 (1,1,2)Custom Key Binary Search
Sometimes the search key is not the stored value itself but a derived property. Python's bisect module does not support a key function directly, but you can binary search manually by applying the key inside the loop. This pattern appears when searching a list of objects by one of their attributes.
# Binary search on a list of (score, name) tuples by score
def lower_bound_by_score(records, min_score):
lo, hi = 0, len(records)
while lo < hi:
mid = lo + (hi - lo) // 2
if records[mid][0] < min_score:
lo = mid + 1
else:
hi = mid
return lo
records = [(50, 'Alice'), (72, 'Bob'), (72, 'Carol'), (88, 'Dave'), (95, 'Eve')]
idx = lower_bound_by_score(records, 72)
print(idx) # 1 (first record with score >= 72)
print(records[idx:]) # [(72,'Bob'),(72,'Carol'),(88,'Dave'),(95,'Eve')]Common Interview Errors with Bounds
The most common mistake is forgetting to validate after calling bisect_left. The function always returns a valid insertion index but does not guarantee the element at that index equals the target. Always check arr[result] == target before assuming the target was found.
A second mistake is using bisect_right when you want the first occurrence — bisect_right returns one past the last occurrence, so subtracting 1 gives the last, not the first.
import bisect
arr = [1, 3, 5, 7]
target = 4
# bisect_left returns 2 (insertion point for 4 between 3 and 5)
idx = bisect.bisect_left(arr, target)
print(idx) # 2
# Validate: arr[2] is 5, not 4 => target absent
found = idx < len(arr) and arr[idx] == target
print('Found:', found) # FalseSummary: When to Use bisect_left vs bisect_right
Use bisect_left when you need: the first occurrence of target, the insertion point that displaces existing copies to the right, or to check if target exists. Use bisect_right when you need: one past the last occurrence, the insertion point after all existing copies, or the count of elements <= target (it equals bisect_right(arr, target)).
Both run in O(log n) and are part of the Python standard library, so you can import and use them directly unless the interviewer asks you to implement from scratch.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: bisect_left finds the first element >= target, bisect_right finds the first element > target (one past the last occurrence), and their difference gives the count of occurrences in O(log n). Next up we explore answer-space binary search where the search space is a range of possible answers, not an array index.
Frequently asked questions
Is the “Lower Bound and Upper Bound” lesson free?
Yes — the full text of “Lower Bound and Upper Bound” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Lower Bound and Upper Bound”?
Implement bisect_left and bisect_right from scratch, then apply them to find first and last positions of a target value. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Lower Bound and Upper Bound” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.