def binary_search(nums, target):
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r - l) // 2
if nums[mid] == target: return mid
elif nums[mid] < target: l = mid + 1
else: r = mid - 1
return -1
Search Insert Position
// C++
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size();
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
return l;
}
First Bad Version
def firstBadVersion(n: int) -> int:
l, r = 1, n
while l < r:
mid = l + (r - l) // 2
if isBadVersion(mid): r = mid
else: l = mid + 1
return l
More Problems
Problem
Pattern
Complexity
Peak Element
Binary search on mountain
O(log n)
Search in Rotated Sorted Array
Find pivot, then binary search
O(log n)
Find Minimum in Rotated Array
Compare mid with right
O(log n)
Median of Two Sorted Arrays
Partitioning, binary search on smaller
O(log(min(m,n)))
✏️ Exercise: Implement Search Insert Position using the "lower bound" pattern. Solve First Bad Version. Aim for bug-free code in <20 min each.