Quảng cáo
3 câu trả lời 71
Để tìm kiếm bạn "Phúc" trong danh sách đã cho bằng thuật toán tìm kiếm nhị phân, ta thực hiện các bước sau:
Sắp xếp danh sách theo thứ tự từ điển.
Chia danh sách thành hai phần, lấy phần giữa.
So sánh tên ở vị trí giữa với "Phúc".
Nếu tên ở vị trí giữa bằng "Phúc", trả về kết quả.
Nếu tên ở vị trí giữa lớn hơn "Phúc", lặp lại quá trình với phần danh sách bên trái.
Nếu tên ở vị trí giữa nhỏ hơn "Phúc", lặp lại quá trình với phần danh sách bên phải.
Danh sách đã được sắp xếp từ điển:
Bình
Đoàn
Hạnh
Hoà
Khanh
Khiêm
Lan
Mai
Minh
Phúc
Bắt đầu tìm kiếm nhị phân:
Lấy phần giữa: "Khanh"
So sánh "Khanh" với "Phúc": "Khanh" > "Phúc"
Tiếp tục tìm kiếm trong danh sách bên trái của "Khanh"
Lấy phần giữa: "Hoà"
So sánh "Hoà" với "Phúc": "Hoà" < "Phúc"
Tiếp tục tìm kiếm trong danh sách bên phải của "Hoà"
Lấy phần giữa: "Lan"
So sánh "Lan" với "Phúc": "Lan" < "Phúc"
Tiếp tục tìm kiếm trong danh sách bên phải của "Lan"
Lấy phần giữa: "Mai"
So sánh "Mai" với "Phúc": "Mai" < "Phúc"
Tiếp tục tìm kiếm trong danh sách bên phải của "Mai"
Lấy phần giữa: "Minh"
So sánh "Minh" với "Phúc": "Minh" < "Phúc"
Tiếp tục tìm kiếm trong danh sách bên phải của "Minh"
Lấy phần giữa: "Phúc"
"Phúc" = "Phúc"
Vậy, bạn "Phúc" được tìm thấy trong danh sách.
1. Sắp xếp danh sách theo thứ tự bảng chữ cái: [Bình, Đoàn, Hạnh, Hoà, Khanh, Khiêm, Lan, Mai, Minh, Phúc].
2. Xác định chỉ số trái (left) ban đầu là 0 và chỉ số phải (right) là độ dài danh sách - 1 (trong trường hợp này, left = 0, right = 9).
3. Lặp lại quá trình tìm kiếm nhị phân như sau:, - Tại mỗi bước, tính chỉ số trung bình (mid) bằng cách lấy trung bình của left và right (mid = (left + right) // 2)., - So sánh phần tử ở chỉ số mid với "Phúc":, + Nếu phần tử tại chỉ số mid là "Phúc", trả về kết quả là mid., + Nếu phần tử tại chỉ số mid nhỏ hơn "Phúc", cập nhật left = mid + 1., + Nếu phần tử tại chỉ số mid lớn hơn "Phúc", cập nhật right = mid - 1.
4. Lặp lại quá trình trên cho đến khi left > right hoặc tìm thấy "Phúc". Nếu không tìm thấy, trả về "Không tìm thấy".
Áp dụng thuật toán trên vào danh sách đã cho, ta sẽ tìm thấy "Phúc" ở chỉ số 9 trong danh sách.
Quảng cáo
Câu hỏi hot cùng chủ đề
-
2 32067
-
Hỏi từ APP VIETJACK3 24455