Binary Search¶
Table of Contents¶
- 704. Binary Search (Easy)
- 35. Search Insert Position (Easy)
- 278. First Bad Version (Easy)
- 34. Find First and Last Position of Element in Sorted Array (Medium)
- 367. Valid Perfect Square (Easy)
- 875. Koko Eating Bananas (Medium)
- 1011. Capacity To Ship Packages Within D Days (Medium)
- 378. Kth Smallest Element in a Sorted Matrix (Medium)
704. Binary Search¶
"""
- Implement binary search algorithm.
"""
from typing import List
# Binary Search [left, right]
def search(nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
return mid
return -1
# Binary Search [left, right)
def search_half_open(nums: List[int], target: int) -> int:
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid
else:
return mid
return -1
# Binary Search (left, right)
def search_open_interval(nums: List[int], target: int) -> int:
left, right = -1, len(nums)
while left + 1 < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid
elif nums[mid] > target:
right = mid
else:
return mid
return -1
if __name__ == "__main__":
nums = [-1, 0, 3, 5, 9, 12]
target = 9
assert search(nums, target) == 4
assert search_half_open(nums, target) == 4
assert search_open_interval(nums, target) == 4
35. Search Insert Position¶
"""
- Return the index of the target if it is found. If not, return the index where it would be if it were inserted in order.
"""
from typing import List
# Binary Search
def searchInsert(nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
return mid
return left
nums = [1, 3, 5, 6]
target = 5
print(searchInsert(nums, target)) # 2
#include <cassert>
#include <vector>
using namespace std;
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return left;
}
};
int main() {
Solution solution;
vector<int> nums = {1, 3, 5, 6};
assert(solution.searchInsert(nums, 5) == 2);
assert(solution.searchInsert(nums, 2) == 1);
assert(solution.searchInsert(nums, 7) == 4);
assert(solution.searchInsert(nums, 0) == 0);
return 0;
}
278. First Bad Version¶
"""
- Find the first bad version given a function `isBadVersion`.
"""
# Binary Search
def firstBadVersion(n: int) -> int:
left, right = 1, n
while left <= right:
mid = left + (right - left) // 2
if isBadVersion(mid):
right = mid - 1
else:
left = mid + 1
return left
def isBadVersion(version: int) -> bool:
pass
34. Find First and Last Position of Element in Sorted Array¶
from bisect import bisect_left
from typing import List
class searchRange:
"""
找 lower bound 和 upper bound
看灵神对这道题的题解，分类讨论区间的写法
target 的 upper bound 是 target + 1 的 lower bound - 1
这样就能统一用 lower bound 的写法
"""
# [left, right]
def bisect_left_closed(self, nums, target):
"""
闭区间写法
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
# [left, right)
def bisect_left_right_open(self, nums, target):
"""
左闭右开区间写法
"""
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
return left
# (left, right)
def bisect_left_open(self, nums, target):
"""
推荐开区间写法
"""
left, right = -1, len(nums)
while left + 1 < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid
else:
right = mid
return right
def search_range(self, nums: List[int], target: int) -> List[int]:
# edge case
if not nums:
return [-1, -1]
lower = self.bisect_left_closed(nums, target)
upper = self.bisect_left_closed(nums, target + 1) - 1
return [lower, upper] if lower <= upper else [-1, -1]
def search_range_bisect(self, nums: List[int], target: int) -> List[int]:
"""用 python bisect 库函数"""
# edge case
if not nums:
return [-1, -1]
lower = bisect_left(nums, target)
upper = bisect_left(nums, target + 1) - 1
return [lower, upper] if lower <= upper else [-1, -1]
if __name__ == "__main__":
nums = [5, 7, 7, 8, 8, 10]
target = 8
sol = searchRange()
assert sol.search_range(nums, target) == [3, 4]
assert sol.search_range_bisect(nums, target) == [3, 4]
#include <vector>
#include <iostream>
using namespace std;
class Solution
{
int bisect_left(vector<int> &nums, int target)
{
int left = 0, right = (int)nums.size() - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] < target)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return left;
}
public:
vector<int> searchRange(vector<int> &nums, int target)
{
int left = bisect_left(nums, target);
if (left == (int)nums.size() || nums[left] != target)
{
return {-1, -1};
}
int right = bisect_left(nums, target + 1) - 1;
return {left, right};
}
};
int main()
{
vector<int> nums = {5, 7, 7, 8, 8, 10};
int target = 8;
Solution s;
vector<int> res = s.searchRange(nums, target);
cout << res[0] << ", " << res[1] << endl;
return 0;
}
367. Valid Perfect Square¶
"""
- Determine if a positive integer is a perfect square without using any built-in library function.
"""
# Binary Search
def isPerfectSquare(num: int) -> bool:
if num < 2:
return True
left, right = 0, num // 2
while left <= right:
mid = left + (right - left) // 2
if mid * mid == num:
return True
elif mid * mid < num:
left = mid + 1
else:
right = mid - 1
return False
num = 16
print(isPerfectSquare(num)) # True
875. Koko Eating Bananas¶
from typing import List
class minEatingSpeed:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
def canEat(piles, k, h):
hours = 0
for pile in piles:
hours += (pile + k - 1) // k
return hours <= h
left, right = 1, max(piles) - 1
while left <= right:
mid = left + (right - left) // 2
if canEat(piles, mid, h):
right = mid - 1
else:
left = mid + 1
return left
if __name__ == "__main__":
piles = [3, 6, 7, 11]
h = 8
sol = minEatingSpeed()
assert sol.minEatingSpeed(piles, h) == 4
1011. Capacity To Ship Packages Within D Days¶
"""
- A conveyor belt has packages that must be shipped from one port to another within `D` days. The `i-th` package has a weight of `weights[i]`. Each day, we load the ship with packages on the conveyor belt. The ship will be loaded with packages up to its capacity. The ship will not be loaded beyond its capacity. Return the least weight capacity of the ship.
"""
from typing import List
# Binary Search
def shipWithinDays(weights: List[int], days: int) -> int:
def canShip(weights, D, capacity):
days = 1
current_weight = 0
for weight in weights:
if current_weight + weight > capacity:
days += 1
current_weight = 0
current_weight += weight
return days <= D
left, right = max(weights), sum(weights)
while left <= right:
mid = left + (right - left) // 2
if canShip(weights, days, mid):
right = mid - 1
else:
left = mid + 1
return left
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
days = 5
print(shipWithinDays(weights, days)) # 15
378. Kth Smallest Element in a Sorted Matrix¶
"""
- Given an `n x n` matrix where each of the rows and columns are sorted in ascending order, return the `k-th` smallest element in the matrix.
"""
from heapq import heapify, heappop, heappush
from typing import List
# Heap - Merge K Sorted
def kthSmallestHeap(matrix: List[List[int]], k: int) -> int:
n = len(matrix)
heap = [(matrix[i][0], i, 0) for i in range(n)]
heapify(heap)
for _ in range(k - 1):
_, row, col = heappop(heap)
if col + 1 < n:
heappush(heap, (matrix[row][col + 1], row, col + 1))
return heappop(heap)[0]
# Binary Search
def kthSmallestBinarySearch(matrix: List[List[int]], k: int) -> int:
n = len(matrix)
def check(mid):
i, j = n - 1, 0
num = 0
while i >= 0 and j < n:
if matrix[i][j] <= mid:
num += i + 1
j += 1
else:
i -= 1
return num >= k
left, right = matrix[0][0], matrix[-1][-1]
while left < right:
mid = (left + right) // 2
if check(mid):
right = mid
else:
left = mid + 1
return left
matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]]
k = 8
print(kthSmallestHeap(matrix, k)) # 13
print(kthSmallestBinarySearch(matrix, k)) # 13