Bài tập  /  Bài đang cần trả lời

Cho danh sách tên sau đây: Hòa Bình Liên Mai Phương Trúc Sơn

Cho danh sách tên sau đây: Hòa, Bình, Liên, Mai, Phương, Trúc, Sơn
a) Sắp xếp tên các bạn theo thứ tự trong bảng chữ cái
b) Em hãy liệt kê các bước lặp tìm kiếm tên “Liên” trong danh sách đã sắp xếp theo thuật toán tìm kiếm nhị phân 
2 Xem trả lời
Hỏi chi tiết
303
1
0
Yến Nguyễn
14/05/2023 20:35:47
+5đ tặng
a) Danh sách tên sau khi sắp xếp theo thứ tự trong bảng chữ cái là:
- Bình
- Hòa
- Liên
- Mai
- Phương
- Sơn
- Trúc

b) Các bước lặp tìm kiếm tên "Liên" trong danh sách đã sắp xếp theo thuật toán tìm kiếm nhị phân như sau:
- Bước 1: Đặt left = 0, right = 6 (tương ứng với vị trí đầu và cuối của danh sách)
- Bước 2: Tính mid = (left + right) // 2 = 3 (chỉ số của tên "Mai" trong danh sách)
- Bước 3: So sánh tên "Liên" với tên tại chỉ số mid, ta thấy "Liên" đứng trước "Mai" trong bảng chữ cái, vì vậy ta đặt right = mid - 1 = 2
- Bước 4: Tính lại mid = (left + right) // 2 = 1 (chỉ số của tên "Hòa" trong danh sách)
- Bước 5: So sánh tên "Liên" với tên tại chỉ số mid, ta thấy "Liên" đứng sau "Hòa" trong bảng chữ cái, vì vậy ta đặt left = mid + 1 = 2
- Bước 6: Tính lại mid = (left + right) // 2 = 2 (chỉ số của tên "Liên" trong danh sách)
- Bước 7: So sánh tên "Liên" với tên tại chỉ số mid, ta thấy tên "Liên" bằng với tên tại chỉ số mid, vì vậy ta tìm thấy tên "Liên" trong danh sách.

Mở khóa để xem toàn bộ nội dung trả lời

(?)
Bạn đã đạt đến giới hạn của mình. Bằng cách Đăng ký tài khoản, bạn có thể xem toàn bộ nội dung trả lời
Cải thiện điểm số của bạn bằng cách đăng ký tài khoản Lazi.
Xem toàn bộ các câu trả lời, chat trực tiếp 1:1 với đội ngũ Gia sư Lazi bằng cách Đăng nhập tài khoản ngay bây giờ
Tôi đã có tài khoản? Đăng nhập
0
0
Đức Anh Trần
14/05/2023 20:36:25
+4đ tặng
a) Sắp xếp tên các bạn theo thứ tự trong bảng chữ cái:
- Bình
- Hòa
- Liên
- Mai
- Phương
- Sơn
- Trúc

b) Liệt kê các bước lặp tìm kiếm tên "Liên" trong danh sách đã sắp xếp theo thuật toán tìm kiếm nhị phân:
1) Bước 1: Đặt chỉ số bắt đầu (left) là 0 và chỉ số kết thúc (right) là 6 (chiều dài của danh sách - 1).
2) Bước 2: Tính chỉ số trung tâm (mid) bằng cách lấy tổng của left và right chia cho 2, làm tròn xuống. mid = floor((left + right) / 2) = floor((0 + 6) / 2) = 3.
3) Bước 3: So sánh tên tại chỉ số trung tâm (names[mid]) với tên "Liên". Tên tại chỉ số trung tâm là "Mai".
   - Vì "Mai" đứng sau "Liên" trong bảng chữ cái, nên "Liên" có thể nằm ở bên trái của tên tại chỉ số trung tâm.
4) Bước 4: Cập nhật chỉ số kết thúc (right) thành mid - 1. right = 3 - 1 = 2.
5) Bước 5: Quay lại bước 2 với left không thay đổi, right = 2.
6) Bước 2: Tính chỉ số trung tâm mới. mid = floor((left + right) / 2) = floor((0 + 2) / 2) = 1.
7) Bước 3: So sánh tên tại chỉ số trung tâm (names[mid]) với tên "Liên". Tên tại chỉ số trung tâm là "Hòa".
   - Vì "Hòa" đứng trước "Liên" trong bảng chữ cái, nên "Liên" có thể nằm ở bên phải của tên tại chỉ số trung tâm.
8) Bước 4: Cập nhật chỉ số bắt đầu (left) thành mid + 1. left = 1 + 1 = 2.
9) Bước 5: Quay lại bước 2 với left > right. Vì left > right, nên thuật toán kết thúc.
10) "Liên" không được tìm thấy trong danh sách.
Đức Anh Trần
Đánh giá điểm giúp mình

Bạn hỏi - Lazi trả lời

Bạn muốn biết điều gì?

GỬI CÂU HỎI
Học tập không giới hạn cùng học sinh cả nước và AI, sôi động, tích cực, trải nghiệm

Hôm nay bạn thế nào? Hãy nhấp vào một lựa chọn, nếu may mắn bạn sẽ được tặng 50.000 xu từ Lazi

Vui Buồn Bình thường
×
Trợ lý ảo Trợ lý ảo
×
Đấu trường tri thức | Lazi Quiz Challenge +500k
Gửi câu hỏi
×