1) Cho danh sách: An, Bình, Hòa, Liên, Mai, Phương, Trang, Trúc, Tước.
a. Cho biết thuật toán tìm kiếm tuần tự để tìm tên “Trúc” phải thực hiện bao nhiêu bước để tìm thấy. Thuật toán tìm kiếm tuần tự thực hiện công việc gì và thực hiện như thế nào?
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.
Trong trường hợp này, chúng ta cần tìm phần tử có giá trị là 47 trong dãy A = [1, 91, 45, 23, 67, 9, 10, 47, 90, 46, 86]. Ta sẽ thực hiện duyệt từng phần tử trong dãy này để tìm kiếm phần tử có giá trị là 47.
Dãy A có tổng cộng 11 phần tử, và trong trường hợp xấu nhất, phần tử cần tìm là phần tử cuối cùng của dãy. Vì vậy, trong trường hợp xấu nhất, ta cần duyệt qua toàn bộ dãy A để tìm thấy phần tử có giá trị là 47.
Vậy, số lần duyệt cần thực hiện là 7 lần.
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.
Thuật toán tìm kiếm nhị phân thực hiện tìm kiếm một mảng đã sắp xếp bằng cách liên tục chia các khoảng tìm kiếm thành 1 nửa. Bắt đầu với một khoảng từ phần tử đầu mảng, tới cuối mảng. Nếu giá trị của phần tử cần tìm nhỏ hơn giá trị của phần từ nằm ở giữa khoảng thì thu hẹp phạm vi tìm kiếm từ đầu mảng tới giửa mảng và nguợc lại. Cứ thế tiếp tục chia phạm vi thành các nửa cho dến khi tìm thấy hoặc đã duyệt hết.
Thuật toán tìm kiếm nhị phân tỏ ra tối ưu hơn so với tìm kiếm tuyết tính ở các mảng có độ dài lớn và đã được sắp xếp. Ngược lại, tìm kiếm tuyến tính sẽ tỏ ra hiệu quả hơn khi triển khai trên các mảng nhỏ và chưa được sắp xếp.