Question

Đã trả lời bởi chuyên gia

Answer 1

Chào , trong hai thuật toán tìm kiếm cơ bản mà chúng ta đã học, thuật toán tìm kiếm nhị phân (Binary Search) là phù hợp nhất để tìm một số trong dãy số đã được sắp xếp như dãy số 34, 45, 53, 57, 67, 69, 72, 75.

Lý do: Thuật toán tìm kiếm nhị phân hoạt động hiệu quả trên các dãy số đã được sắp xếp. Nó liên tục chia đôi phần dãy số cần tìm kiếm cho đến khi tìm thấy số cần tìm hoặc xác định được số đó không có trong dãy. Điều này giúp giảm đáng kể số lần so sánh so với thuật toán tìm kiếm tuyến tính (duyệt từng phần tử).

Mô tả thuật toán tìm kiếm nhị phân để tìm số 72 trong dãy số trên:

Đầu vào:

Dãy số đã sắp xếp: [34, 45, 53, 57, 67, 69, 72, 75]
Số cần tìm: 72
Các bước thực hiện:

Xác định phạm vi tìm kiếm ban đầu:

left = 0 (chỉ số của phần tử đầu tiên trong dãy)
right = 7 (chỉ số của phần tử cuối cùng trong dãy, vì dãy có 8 phần tử)
Lặp cho đến khi left > right (tức là phạm vi tìm kiếm trở nên rỗng):

Tính chỉ số ở giữa (mid): mid = (left + right) // 2 (phép chia lấy phần nguyên)
So sánh phần tử tại chỉ số mid với số cần tìm:
Nếu dãy_số[mid] bằng với số cần tìm (72), thì đã tìm thấy.
Nếu dãy_số[mid] nhỏ hơn số cần tìm (72), thì số cần tìm nằm ở nửa bên phải của dãy. Cập nhật left = mid + 1.
Nếu dãy_số[mid] lớn hơn số cần tìm (72), thì số cần tìm nằm ở nửa bên trái của dãy. Cập nhật right = mid - 1.
Bảng mô tả các lần lặp:

Lần lặp left right mid dãy_số[mid] So sánh với 72 Kết quả
1 0 7 (0+7)//2=3 57 57 < 72 left = 3 + 1 = 4
2 4 7 (4+7)//2=5 69 69 < 72 left = 5 + 1 = 6
3 6 7 (6+7)//2=6 72 72 == 72 Đúng số cần tìm

Xuất sang Trang tính
Kết luận: Thuật toán tìm kiếm nhị phân đã tìm thấy số 72 ở lần lặp thứ 3.

Lưu ý: Nếu sau tất cả các lần lặp mà không tìm thấy số cần tìm (khi left > right), thì số đó không tồn tại trong dãy. Trong trường hợp này, vì số 72 có trong dãy, thuật toán đã dừng lại khi tìm thấy.

...Xem thêm

Answer 2