em hãy vận dụng thuật toán tìm kiếm nhị phân để tìm ra vị trí của số 10 trong danh sách [2;6;8;10;12;9;14;5]. Giúp mik với,mik cần gấp lắm ạ
K
Khách
Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.
Những câu hỏi liên quan
QT
Quoc Tran Anh Le
Giáo viên
9 tháng 11 2023
Sau lần chia đôi đầu tiên, pham vi tìm kiếm còn lại n/2 số, sau khi chia đôi lần thứ hai, dãy còn lại n/4 số, sau khi chia đôi lần thứ dãy còn lại n/8, …sau khi chia đôi lần k dãy còn lại n/2.mũ k. Kết thúc khi 2 mũ k sấp xỉ n.
QT
Quoc Tran Anh Le
Giáo viên
9 tháng 11 2023
a. Ví dụ một bài toán tìm kiếm trong thực tế: Giáo viên muốn tìm tên bạn Chung trong danh sách lớp sau:
Các bước thực hiện thuật toán tìm kiếm nhị phân cho bài toán trên:
- Bước 1: Xét vị trí ở giữa dãy, đó là vị trí số 5
- Vì sau bước 2 đã tìm thấy tên học sinh nên thuật toán kết thúc.
b) Thuật toán tìm kiếm nhị phân
- Thuật toán tìm kiếm nhị phân thu hẹp được phạm vi tìm kiếm chỉ còn tối đa là một nửa sau mỗi lần lặp. Thuật toán chia bài toán thành những bài toán nhỏ hơn giúp tăng hiệu quả tìm kiếm.
Thuật toán tuần tự
- Mô tả thuật toán phải cụ thể, rõ ràng, đầy đủ, đầu vào là gì, đầu ra là gì và chỉ rõ sự kết thúc thuật toán.
- Cần mô tả thuật toán cho tốt thì người máy hay máy tính mới hiểu đúng và thực hiện được.
- Nếu không, kết quả thực hiện thuật toán có thể không như mong đợi.
QT
Quoc Tran Anh Le
Giáo viên
21 tháng 8 2023
Ý tưởng: cho trước một dãy số và tìm số x nằm ở vị trí nào trong dãy số đó.
Danh sách sau khi sắp xếp:
\(2;5;6;8;9;10;12;14\)
Lần lặp 1:
- Chia đôi danh sách:
Ta có vị trí đang xét có giá trị là 8
- So sánh 10 > 8 nên ta bỏ phần phía trước, lấy phần phía sau gồm các số 9; 10; 12; 14
* Lần lặp 2:
- Chia đôi danh sách còn lại ở lần lặp 1 như sau:
Ta có vị trí đang xét là số 10
- So sánh 10 = 10 nên thông báo tìm thấy số 10 sau lần lặp thứ 2 và kết thúc thuật toán.