Vận dụngCâu hỏi 1. Cho dãy các số A = (3, 1, 0, 10, 13, 16, 9, 7, 5, 11].a) Viết chương trình mô tả...

Cách làm:

a)
- Viết chương trình sử dụng vòng lặp để duyệt từng phần tử trong dãy A.
- Kiểm tra nếu phần tử đó bằng với số cần tìm (C = 9) thì trả về vị trí của nó trong dãy.
- Nếu không tìm thấy, trả về -1.

b)
- Viết chương trình tìm kiếm nhị phân cho dãy đã sắp xếp.
- Sử dụng thuật toán nhị phân để tìm kiếm phần tử C = 9.
- Đo thời gian thực hiện thuật toán để so sánh kết quả với cách tìm kiếm thông thường.

Câu trả lời:
a)
- Viết chương trình sử dụng vòng lặp để duyệt từng phần tử trong dãy A.
- Kiểm tra nếu phần tử đó bằng với số cần tìm (C = 9) thì trả về vị trí của nó trong dãy.
- Nếu không tìm thấy, trả về -1.
- Thời gian thực hiện tìm kiếm theo cách này là O(n) trong trường hợp xấu nhất khi số cần tìm đứng cuối cùng trong dãy.

b)
- Viết chương trình tìm kiếm nhị phân cho dãy đã sắp xếp.
- Sử dụng thuật toán nhị phân để tìm kiếm phần tử C = 9.
- Đo thời gian thực hiện thuật toán để so sánh kết quả với cách tìm kiếm thông thường.
- Thời gian thực hiện tìm kiếm theo cách nhị phân là O(log n) trong trường hợp xấu nhất.
- So sánh kết quả giữa cả hai cách tìm kiếm để nắm rõ hiệu suất của từng phương pháp.