Giao diện
Binary Search và các biến thể
🎯 Mục tiêu
Luyện tập Binary Search cổ điển, tìm cận dưới/cận trên, tìm kiếm trên mảy xoay và ma trận 2D sắp xếp.
Yêu cầu
Bài 1: Binary Search cổ điển
Cài đặt tìm kiếm nhị phân trả về chỉ số của phần tử cần tìm, hoặc -1 nếu không tồn tại.
python
def binary_search(arr: list[int], target: int) -> int:
# Tìm vị trí của target trong mảng đã sắp xếp
pass
assert binary_search([1, 3, 5, 7, 9, 11], 7) == 3
assert binary_search([1, 3, 5, 7, 9, 11], 4) == -1Bài 2: Lower Bound và Upper Bound
Cài đặt hàm tìm vị trí chèn đầu tiên (lower bound) và vị trí sau phần tử cuối cùng bằng target (upper bound).
python
def lower_bound(arr: list[int], target: int) -> int:
# Tìm chỉ số nhỏ nhất i sao cho arr[i] >= target
pass
def upper_bound(arr: list[int], target: int) -> int:
# Tìm chỉ số nhỏ nhất i sao cho arr[i] > target
pass
arr = [1, 2, 2, 2, 3, 5]
assert lower_bound(arr, 2) == 1
assert upper_bound(arr, 2) == 4Bài 3: Tìm kiếm trong mảng xoay
Cho mảng đã sắp xếp rồi xoay tại một điểm, tìm phần tử target.
python
def search_rotated(arr: list[int], target: int) -> int:
# Tìm target trong mảng đã sắp xếp và xoay. Trả về -1 nếu không tìm thấy
pass
assert search_rotated([4, 5, 6, 7, 0, 1, 2], 0) == 4
assert search_rotated([4, 5, 6, 7, 0, 1, 2], 3) == -1Bài 4: Tìm kiếm trong ma trận 2D
Cho ma trận m×n trong đó mỗi hàng và cột được sắp xếp tăng dần, tìm target.
python
def search_matrix(matrix: list[list[int]], target: int) -> bool:
# Tìm target trong ma trận đã sắp xếp theo hàng và cột
pass
matrix = [[1,4,7],[2,5,8],[3,6,9]]
assert search_matrix(matrix, 5) == True
assert search_matrix(matrix, 10) == FalsePhân tích độ phức tạp
| Bài | Time | Space |
|---|---|---|
| 1 - Binary Search | O(log n) | O(1) |
| 2 - Lower/Upper Bound | O(log n) | O(1) |
| 3 - Rotated Array | O(log n) | O(1) |
| 4 - Ma trận 2D | O(m + n) | O(1) |
Gợi ý
Gợi ý Bài 2
Lower bound: khi rr[mid] >= target, thu hẹp sang trái ( ight = mid). Upper bound: khi rr[mid] > target, thu hẹp sang trái.
Gợi ý Bài 3
Xác định nửa nào đã sắp xếp (so sánh rr[left] với rr[mid]), sau đó kiểm tra target có nằm trong nửa đã sắp xếp không.
Gợi ý Bài 4
Bắt đầu từ góc trên-phải. Nếu giá trị lớn hơn target → di chuyển sang trái, nếu nhỏ hơn → di chuyển xuống dưới.
Lời giải tham khảo
Xem lời giải
python
def binary_search(arr: list[int], target: int) -> int:
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target: return mid
elif arr[mid] < target: left = mid + 1
else: right = mid - 1
return -1
def lower_bound(arr: list[int], target: int) -> int:
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] < target: left = mid + 1
else: right = mid
return left
def search_rotated(arr: list[int], target: int) -> int:
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 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 search_matrix(matrix: list[list[int]], target: int) -> bool:
if not matrix: return False
row, col = 0, len(matrix[0]) - 1
while row < len(matrix) and col >= 0:
if matrix[row][col] == target: return True
elif matrix[row][col] > target: col -= 1
else: row += 1
return False