Tìm Kiếm Nhị Phân Cổ ĐiểnBinary Search
Hiểu bài
Cho bạn một mảng số nguyên nums đã sắp xếp tăng dần và số nguyên target. Tìm chỉ số của target trong mảng. Nếu không có, trả về -1.
Ví dụ:
nums = [-1, 0, 3, 5, 9, 12], target = 9
output = 4 // nums[4] = 9
nums = [-1, 0, 3, 5, 9, 12], target = 2
output = -1 // 2 không có trong mảngTìm kiếm nhị phân cắt đôi không gian tìm kiếm mỗi bước — đây là cách biến O(n) thành O(log n).
Chỉ áp dụng được khi mảng đã sắp xếp.
Xem cách cơ bản (chậm hơn)
O(n) time, O(1) spacefunction search(nums: number[], target: number): number {
for (let i = 0; i < nums.length; i++) {
if (nums[i] === target) return i
}
return -1
}Duyệt tuần tự từ đầu đến cuối — bỏ qua hoàn toàn thông tin mảng đã sắp xếp.
Với n=10⁶ phần tử, tìm kiếm nhị phân chỉ cần ~20 bước thay vì 10⁶ bước.
Lời giải tối ưu
O(log n) time, O(1) spacefunction search(nums: number[], target: number): number {
let low = 0
let high = nums.length - 1
while (low <= high) {
const mid = Math.floor((low + high) / 2)
if (nums[mid] === target) return mid
if (nums[mid] < target) low = mid + 1 // target nằm nửa phải
else high = mid - 1 // target nằm nửa trái
}
return -1
}Cách tối ưu: mỗi bước so sánh phần tử giữa với target, loại bỏ nửa không cần thiết.
- Sau log₂(n) bước, không gian tìm kiếm thu về 0.
- Dùng
Math.floor((low + high) / 2)thay vì(low + high) >> 1để tránh integer overflow ở ngôn ngữ khác.
Chạy thử từng bước
- 1
nums=[-1,0,3,5,9,12], target=9. low=0, high=5. mid=2, nums[2]=3 < 9 → low=3.
low:0high:5mid:2midVal:3action:"low=3" - 2
low=3, high=5. mid=4, nums[4]=9 === target → return 4.
low:3high:5mid:4midVal:9result:4
Trường hợp biên phải nhớ
Mảng 1 phần tử — low=high=0, mid=0, so sánh một lần duy nhất.
Target nhỏ hơn mọi phần tử — high sẽ về -1 trước khi low, vòng lặp kết thúc, return -1.
Target lớn hơn mọi phần tử — low sẽ vượt quá high, return -1.
Mảng rỗng — high=-1 < low=0 ngay từ đầu, vòng lặp không chạy, return -1.
Phần tử trùng nhau — đề không đảm bảo phần tử duy nhất, nhưng tìm kiếm nhị phân cổ điển chỉ trả về 1 chỉ số bất kỳ.