Có bao giờ bạn phải đau đầu vì để quên chiếc ví ở đâu đó trong nhà mà tìm mãi không thấy? Hay việc các bạn nữ luôn không thể nào tìm thấy bộ quần áo phù hợp để lên phố mặc dù số lượng trang phục xếp nặng trĩu trong tủ quần áo? Cuộc sống chúng ta luôn gắn liền với việc tìm kiếm. Từ một đứa trẻ tò mò tìm kiếm khám phá từng điều thú vị của thế giới đến khi trưởng thành chúng ta phải chật vật tìm kiếm một nửa mảnh ghép còn lại của đời mình, mà ... có nhiều người còn phải chịu thua số phận và đành cam lòng gắn lên mình danh hiệu "FA".
Đừng nản chí, để giúp bạn giải quyết những vấn đề đó, hôm nay chúng ta sẽ cùng khám phá về thuật toán tìm kiếm trong lập trình - một giải thuật quen thuộc, hữu ích vô cùng trong Tin học mà còn có thể áp dụng ra đời sống, giúp bạn tìm thấy chân ái của đời mình!
2. Bài toán tìm kiếm trong Tin học
Cùng so sánh hai sự việc sau đây:
- Bạn đang cần tìm cục tẩy trong hộp bút.
- Tìm kiếm số 66 ở vị trí nào trong một dãy số cho trước.
Mục tiêu tìm kiếm trong cả hai bài toán đều đã được xác định, đó là "cục tẩy" và "số 66" [cần tìm thấy số 66 xong mới có được vị trí]. Và tập "dữ liệu" của chúng ta có [hay phạm vi tìm kiếm] chính là "những đồ vật trong hộp bút" hoặc "các số trong dãy số đã cho trước". Có thể hiểu, tìm kiếm là quá trình tìm một phần tử nằm trong một tập hợp rất nhiều phần tử dựa vào một yêu cầu nào đó.
Trong Tin học, với sự giúp đỡ của máy tính, rất nhiều thuật toán tìm kiếm đã ra đời với tính hiệu quả ngày càng tăng cao. Những thuật toán tìm kiếm cơ bản nhất có thể kể đến là Tìm kiếm tuần tự và Tìm kiếm nhị phân. Ngoài ra, áp dụng thêm những cấu trúc dữ liệu trong khi tìm kiếm có thể cho ra những thuật toán có hiệu quả cao hơn nữa.
Bài toán tìm kiếm trong Tin học có thể phát biểu như sau: "Cho một dãy gồm nn đối tượng a1,a2,...,ana_1, a_2,..., a_n. Mỗi đối tượng aia_i có một khóa key [1≤i≤n]key \ [1 \le i \le n] gọi là khóa tìm kiếm. Cần tìm kiếm đối tượng có khóa bằng kk cho trước, tức là ai.key=ka_i.key = k". Quá trình tìm kiếm sẽ hoàn thành nếu như có một trong hai trường hợp sau đây xảy ra:
- Tìm được đối tượng có khóa tương ứng bằng k,k, khi đó phép tìm kiếm thành công.
- Không tìm được đối tượng nào có khóa tương ứng bằng k,k, khi đó phép tìm kiếm thất bại.
Dưới đây, tôi sẽ trình bày một số thuật toán thông dụng để giải quyết bài toán trên!
II. Giải thuật tìm kiếm tuần tự [Sequential Search]
Ý tưởng
Tìm kiếm tuần tự [Sequential Search hay Linear Search] là một giải thuật đơn giản, rất dễ cài đặt. Bắt đầu từ đối tượng a1,a_1, duyệt qua tất cả các đối tượng, cho tới khi tìm thấy đối tượng có khóa mong muốn, hoặc duyệt hết toàn bộ dãy mà không tìm thấy khóa đó.
Mô phỏng giải thuật C++:
sequential_search[a[], n, k]
{
for [i = 1; i k;
int a[n + 1];
for [int i = 1; i > a[i];
cout k thì nghĩa là đoạn từ amida_{mid} tới ara_r chỉ chứa toàn các đối tượng có khóa lớn hơn k,k, nên ta tiếp tục quá trình tìm kiếm trên đoạn từ ala_l tới amid−1a_{mid - 1}.Nếu amid.key=ka_{mid}.key = k thì quá trình tìm kiếm thành công. Quá trình tìm kiếm sẽ thất bại nếu như đến một bước nào đó, tập tìm kiếm bị rỗng [l>r][l > r].
Mô phỏng giải thuật C++:
binary_search[a, k]
{
// Sắp xếp lại các đối tượng tăng dần theo khóa tìm kiếm.
sort[a];
l = 1, r = n;
// Trong khi tập tìm kiếm chưa rỗng th
while [l