Luyện tập tự luận SVIP

Hướng dẫn giải:

Thuật toán tìm kiếm tuần tự là thuật toán thực hiện so sánh lần lượt từ phần tử đầu tiên của dãy với giá trị cần tìm, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.

Hướng dẫn giải:

- Thuật toán tìm kiếm nhị phân chỉ áp dụng cho dãy giá trị đã được sắp xếp.

- Thuật toán tìm kiếm nhị phân là một vòng lặp, ở mỗi lần lặp ta thực hiện:

+ Bước 1: So sánh giá trị cần tìm với giá trí của phần tử giữa dãy đang xét.

+ Bước 2: Nếu bằng nhau thì thông báo vị trí tìm thấy và kết thúc.

+ Bước 3: Nếu nhỏ hơn thì xét dãy ở nửa trước và ngược lại.

+ Bước 4: Nếu dãy rỗng thì thông báo không tìm thấy và kết thúc tìm kiếm, nếu không thì lặp lại từ bước 1.

Hướng dẫn giải:

Một số điểm khác nhau giữa thuật toán tìm kiếm tuần tự và thuật toán tìm kiếm nhị phân:

- Thuật toán tìm kiếm tuần tự có thể áp dụng với bất kỳ dãy nào, kể cả khi dãy chưa được sắp xếp. Trong khi đó, thuật toán tìm kiếm nhị phân chỉ hoạt động chính xác khi dãy đã được sắp xếp theo một trật tự xác định, thường là tăng dần.

- Tìm kiếm tuần tự tiến hành kiểm tra từng phần tử trong dãy, bắt đầu từ đầu đến cuối. Ngược lại, tìm kiếm nhị phân luôn bắt đầu bằng việc so sánh phần tử ở giữa dãy với giá trị cần tìm, sau đó tiếp tục tìm kiếm ở nửa dãy phù hợp tùy vào kết quả so sánh.

 - Khi sử dụng thuật toán tìm kiếm tuần tự, trong trường hợp xấu nhất, ta có thể phải kiểm tra tất cả các phần tử trong dãy. Ngược lại, với tìm kiếm nhị phân, mỗi bước sẽ loại bỏ được một nửa số lượng phần tử, do đó giảm đáng kể số lần cần kiểm tra.

- Tìm kiếm tuần tự thường chậm hơn, đặc biệt với các dãy dữ liệu dài, do phải duyệt qua toàn bộ dãy. Trong khi đó, tìm kiếm nhị phân nhanh hơn rõ rệt trong những dãy lớn đã được sắp xếp, vì số lần kiểm tra giảm theo cấp số nhân.

Hướng dẫn giải:

Sử dụng thuật toán tìm kiếm nhị phân là phù hợp nhất để tìm một số trong dãy số này vì đây là dãy số sắp xếp tăng dần, số lần lặp phải thực hiện ít hơn hẳn so với khi sử dụng thuật toán tìm kiếm tuần tự (ta sẽ thấy rõ khi dãy có nhiều phần tử và phần tử cần tìm cách xa phần tử đầu tiên).