Câu 20. trình bày Thuật toán tìm kiếm nhị phân
Quảng cáo
2 câu trả lời 48
Thuật toán tìm kiếm nhị phân (Binary Search):
Điều kiện:
Dãy phải được sắp xếp tăng hoặc giảm
Ý tưởng:
So sánh giá trị cần tìm với phần tử ở giữa dãy, sau đó loại bỏ một nửa dãy không cần xét.
Các bước thực hiện:
Xác định:left = đầu dãy
right = cuối dãy
Tính vị trí giữa:mid = (left + right) / 2
So sánh:Nếu A[mid] = x → tìm thấy
Nếu A[mid] > x → tìm bên trái (right = mid - 1)
Nếu A[mid] < x → tìm bên phải (left = mid + 1)
Lặp lại đến khi tìm thấy hoặc left > right
Ví dụ:
Dãy: 2, 4, 6, 8, 10 (tìm 8)
mid = 6 → nhỏ hơn → tìm bên phải
mid = 8 → tìm thấy
Nhanh hơn tìm kiếm thường
Độ phức tạp: O(log n)
Quảng cáo
Bạn cần hỏi gì?
Câu hỏi hot cùng chủ đề
-
Đã trả lời bởi chuyên gia
61633 -
Đã trả lời bởi chuyên gia
33063 -
Hỏi từ APP VIETJACK
Đã trả lời bởi chuyên gia
25274 -
Đã trả lời bởi chuyên gia
23844
