a. Hãy sắp xếp danh sách trên theo thứ tự tăng dần?
b. Em hãy viết các bước lặp thực hiện thuật toán tìm kiếm nhị phân để tìm số 5?
Quảng cáo
2 câu trả lời 140
DANH SÁCH BAN ĐẦU:
8 5 9 25 3
a. Sắp xếp danh sách theo thứ tự tăng dần:
Ta sắp xếp lại danh sách:
3 5 8 9 25
b. Các bước lặp thuật toán tìm kiếm nhị phân để tìm số 5 trong danh sách đã sắp xếp:
Danh sách đã sắp xếp: 3 5 8 9 25
Chỉ số tương ứng: 0 1 2 3 4
Bước 1:
left = 0, right = 4
Tính mid = (0 + 4) // 2 = 2 → a[mid] = 8
So sánh: 5 < 8 → Tìm tiếp bên trái
→ Cập nhật: right = mid - 1 = 1
Bước 2:
left = 0, right = 1
Tính mid = (0 + 1) // 2 = 0 → a[mid] = 3
So sánh: 5 > 3 → Tìm tiếp bên phải
→ Cập nhật: left = mid + 1 = 1
Bước 3:
left = 1, right = 1
Tính mid = (1 + 1) // 2 = 1 → a[mid] = 5
Tìm thấy số 5 tại vị trí chỉ số 1
DANH SÁCH BAN ĐẦU:
8 5 9 25 3
a. Sắp xếp danh sách theo thứ tự tăng dần:
Ta sắp xếp lại danh sách:
3 5 8 9 25
b. Các bước lặp thuật toán tìm kiếm nhị phân để tìm số 5 trong danh sách đã sắp xếp:
Danh sách đã sắp xếp: 3 5 8 9 25
Chỉ số tương ứng: 0 1 2 3 4
Bước 1:
left = 0, right = 4
Tính mid = (0 + 4) // 2 = 2 → a[mid] = 8
So sánh: 5 < 8 → Tìm tiếp bên trái
→ Cập nhật: right = mid - 1 = 1
Bước 2:
left = 0, right = 1
Tính mid = (0 + 1) // 2 = 0 → a[mid] = 3
So sánh: 5 > 3 → Tìm tiếp bên phải
→ Cập nhật: left = mid + 1 = 1
Bước 3:
left = 1, right = 1
Tính mid = (1 + 1) // 2 = 1 → a[mid] = 5
Tìm thấy số 5 tại vị trí chỉ số 1
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
61571 -
Đã trả lời bởi chuyên gia
33005 -
Hỏi từ APP VIETJACK
Đã trả lời bởi chuyên gia
25239 -
Đã trả lời bởi chuyên gia
23799
