Question Bank
Binary Search Fundamentals
Difficulty: Easy
Lower bound, upper bound, and the off-by-one corners of classic binary search. Code stems are Python.
Binary Search Fundamentals
Lower bound, upper bound, and the off-by-one corners of classic binary search. Code stems are Python.
Question Bank
Easy
Python
4 questions
binary-search
binary-search-templates
algorithms
quiz
1,202 views
29
Implement classic binary search over a sorted array. Return the index of target, or -1 if not present.
Examples
Example 1:
Input: nums = [1, 3, 5, 7, 9], target = 5
Output: 2
Explanation: Closed [lo, hi] template. mid = 2, nums[2] = 5, match, return 2. O(log n) because each step halves the active window.Example 2:
Input: nums = [1, 3, 5, 7, 9], target = 6
Output: -1
Explanation: The pointers converge without ever finding 6, so the function returns -1.Define lower bound and upper bound for a sorted array and target. What does each return when target is absent?
Implement lower_bound(nums, target) from scratch without using bisect.
Examples
Example 1:
Input: nums = [1, 2, 4, 4, 5], target = 4
Output: 2
Explanation: lower_bound returns the leftmost index whose value is >= target. Half-open [lo, hi) template: lo moves to mid + 1 when nums[mid] < target; else hi = mid. Loop ends with lo == hi = 2.Example 2:
Input: nums = [1, 2, 4, 4, 5], target = 3
Output: 2
Explanation: 3 is not present, so the answer is the insertion point. Both 4s sit at index 2 onward, so the insertion point is 2.Why does the loop condition while lo < hi (with hi = n) terminate, and how do you know mid is never out of bounds?