Nêu ý tưởng thuật toán tìm kiếm tuần tự, tìm kiếm nhị phân

Câu 2:

a) Ý tưởng thuật toán: Xét dãy số cần tìm có n phần tử: a[0], a[1], a[2]... a[n-1]. Giá trị cần tìm là x.

- Bắt đầu từ khoá đầu tiên, lần lượt so sánh khoá x với khoá tương ứng trong dãy.

- Quá trình tìm kiếm kết thúc khi tìm được khoá thoả mãn hoặc đi đến hết dãy hoặc gặp điều kiện dừng vòng lặp. Đây là kĩ thuật tìm kiếm cổ điển nhất trên 1 danh sách chưa được sắp xếp. Nội dung cơ bản của phương pháp này là duyệt từ phần tử thứ nhất cho tới bản ghi cuối cùng, và so sánh lần lượt với khoá X cần tìm, trong quá trình duyệt nếu có bản ghi trùng với giá trị của X thì chúng ta đưa ra vị trí của bản ghi trong dãy, nếu duyệt tới cuối cùng mà không có bản ghi nào trùng giá trị thì quá trình tìm kiếm không thành công.

b) Hai khả năng xảy ra khi kết thúc tìm kiếm tuần tự là tìm thấy hoặc xét hết dãy và không tìm thấy kết quả cần tìm kiếm.

Câu 3:

a) Giả sử bạn đang có một mảng A bao gồm n phần tử, bạn đang cần tìm kiếm phần tử ở x.

Ý tưởng của thuật toán tìm kiếm nhị phân đó là mỗi lần thực hiện chúng ta sẽ chia mảng ra làm 2 phần, lấy ra phần tử y ở chính giữa và đem phần tử này so sánh với phần tử x cần tìm. Nếu y=x tìm thấy phần tử, ngược lại tiếp tục thực hiện chia mảng đối với mảng con bên trái hoặc mảng con bên phải tùy thuộc vào y<x hay y>x. Thuật toán kết thúc khi tìm thấy phần tử hoặc mảng con không thể chia nhỏ.

Theo như ý tưởng thuật toán ta sẽ lấy ra phần tử y là phần tử chốt và so sánh phần tử chốt này với x cần tìm, mục đích của việc này là kiểm tra xem x nằm ở bên phải hay bên trái mảng so với phần tử chốt là Y. Tức là thuật toán tìm kiếm nhị phân chỉ có thể thực hiện trên mảng đã được sắp xếp(sắp xếp tăng dần hoặc giảm dần), và đây cũng chính là một nhược điểm của thuật toán tìm kiếm này.