Lúc đầu nghe khái niệm về Binary Search và ví dụ đầu tiên của binary search tôi nghĩ binary search thật đơn giản:
Initial Array: [8, 16, 23, 38, 45, 56, 72, 84, 91, 100]
Target: 72
Step 1:
left = 0, right = 9
Middle element index = (0 + 9) / 2 = 4
Middle element = 45
Step 2:
45 < 72 (target)
New search range: [56, 72, 84, 91, 100]
left = 5, right = 9
Middle element index = (5 + 9) / 2 = 7
Middle element = 84
Step 3:
84 > 72 (target)
New search range: [56, 72]
left = 5, right = 6
Middle element index = (5 + 6) / 2 = 5
Middle element = 56
Step 4:
56 < 72 (target)
New search range: [72]
left = 6, right = 6
Middle element index = (6 + 6) / 2 = 6
Middle element = 72
Step 5:
72 == 72 (target)
Element found at index 6.
Nhưng mà ví dụ này đã đơn giản hóa khái niệm về binary search bằng cách dùng mảng đã được sort. Mọi việc đã trở nên rất đơn giản.
Thử xét bài toán sau:
A conveyor belt has packages that must be shipped from one
port to another within days days. The ith package on the
conveyor belt has a weight of weights[i]. Each day, we load
the ship with packages on the conveyor belt (in the order
given by weights). We may not load more weight than the
maximum weight capacity of the ship. Return the least weight
capacity of the ship that will result in all the packages on
the conveyor belt being shipped within days days.
Example 1:
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10
Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.
Example 2:
Input: weights = [3,2,2,4,1,4], days = 3
Output: 6
Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4
Example 3:
Input: weights = [1,2,3,1,1], days = 4
Output: 3
Explanation:
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1
Lúc đầu tiếp cần 1 bài toán như thế này mà bạn chưa từng biết về binary search. Sẽ khá khó để hình dung binary search vào bài toán này như thế nào.
Về cơ bản chúng ta có thể áp dụng được binary search khi:
∀x,y ∈ S, y > x ∧ P(x) = true ⇒ P(y) = true
Được giải thích như sau: nếu x hợp lệ thì mọi phần tử y > x đều hợp lệ. Tính chất này giúp chúng ta loại đi nửa sau của không gian tìm kiếm do đã biết chắc x là phần tử nhỏ nhất trong nửa sau hợp lệ, ta ghi nhận x là kết quả tạm thời và tiếp tục tìm xem có phần tử nào ở nửa đầu (nhỏ hơn x) hợp lệ hay không. Tương tự:
∀x,y ∈ S, y < x ∧ P(x) = false ⇒ P(y) = false
Áp dụng vào bài toán trên. Thực chất chúng ta đang tìm 1 số (M) nhỏ nhất mà khi P(M) đúng thì ta biết chắc chắn P(M+1) sẽ đúng (Capacity tăng thì số ngày cần vận chuẩn days càng giảm). Việc cần làm sẽ là tìm hàm điều kiện P:
Pseudo:
function shipWithinDays(weights, days):
lo = 0
hi = 0
for each w in weights:
if w > lo:
lo = w
hi += w
while hi > lo:
mid = (hi + lo) / 2
if check(weights, mid, days):
hi = mid
else:
lo = mid + 1
return lo
function check(weights, max, days):
days--
count = 0
for each w in weights:
if count + w <= max:
count += w
else:
days--
count = w
return days >= 0
Go:
func shipWithinDays(weights []int, days int) int {
lo, hi := 0, 0
for _, w := range weights {
if w > lo {
lo = w
}
hi += w
}
for hi > lo {
mid := (hi + lo) / 2
if check(weights, mid, days) {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}
func check(weights []int, max int, days int) bool {
days--
count := 0
for _, w := range weights {
if count + w <= max {
count += w
} else {
days--
count = w
}
}
return days >= 0
}