Thuật toán tìm kiếm
Khái niệm về thuật toán tìm kiếm
Thuật toán tìm kiếm là một tập hợp các hành động giúp chúng ta tìm ra kết quả của một bài toán, tuân theo một quy luật chung. Thuật toán này được thực hiện trên ý tưởng thâu tóm vấn đề chung của các dữ liệu trong trường hợp bài toán không thể rút ra đáp án ngay lập tức.
Khi bạn tới thư viện lần đầu, bạn không thể biết ngay cuốn sách mình cần ở đâu. Bỏ qua trường hợp bạn hỏi người quản lí, trong trường hợp xấu nhất bạn sẽ phải nhìn qua bìa sách của từng cuốn một cho đến khi tìm được nó. Đây chính xác là một thuật toán tìm kiếm.
Một vài thuật toán tìm kiếm cơ bản
Tìm kiếm tuyến tính
Duyệt từ đầu đến cuối, bao giờ gặp thì dừng lại.
Độ phức tạp: $O(N)$
Đây là thuật toán tìm kiếm đơn giản nhất bạn có thể nghĩ ra mà không cần kĩ năng hay kế hoạch phức tạp gì cả. Trong trường hợp thư viện kể trên sắp xếp kệ sách 1 cách lộn xộn, bạn vẫn còn một cách để tìm đó là tìm kiếm tuyến tính. Trong thực tế, nó là phương pháp được sử dụng nhiều nhất, và cũng là phương pháp cuối cùng mà bạn có thể dùng.
Implementation của thuật toán này khá đơn giản:
int linear_search()
{
int n; // n is the right_most value
for (int i = 1; i <= n; i++) // suggest that the left_most value is 1
{
if (correct(i)) return i;
}
}Tìm kiếm nhị phân
Chia đôi không gian sau mỗi lần chia, loại bỏ phần không thể chứa kết quả.
Độ phức tạp: $O(logN)$
Giờ hãy giả sử thư viện chúng ta đang nhắc tới sắp xếp những quyển sách theo số trang mà chúng có, và quyển sách của bạn chứa 250 trang. Bạn đoán đúng rồi, chúng ta không cần bắt đầu từ đầu và kết thúc ở cuối dãy sách, sẽ có một khoảng nào đó của kệ sách chỉ chứa những quyển có chính xác 250 trang, ta chỉ cần quan tâm tới nó mà thôi.
Vậy cụ thể ta sẽ tìm khoảng này như thế nào? Sau đây là cách làm bằng tìm kiếm nhị phân.
- Đầu tiên, hãy chắc chắn là dữ liệu đã được sắp xếp tăng dần.
- Gọi vị trí đầu là cuối là $left$ và $right$. Tại mỗi bước, ta lấy vị trí $mid = \left \lfloor \frac{left + right}{2} \right \rfloor$ và xác định dữ liệu tại vị trí đó.
- Gọi $x$ là dữ liệu tại vị trí $mid$, $t$ là giá trị chúng ta đang tìm kiếm. Nếu $x > t$, đặt $right = t - 1$. Nếu $x < t$, đặt $left = t + 1$. Còn nếu $x = t$, ta có luôn đáp án.
- Tiếp tục lặp lại quy trình đến khi chỉ còn $1$ đơn vị trong phạm vi tìm kiếm.
Áp dụng vào ví dụ trên, giả sử kệ sách có số trang sách như sau:$$[100, 150, 150, 180, 200, 200, 230, 230, 250, 250, 300, 320, 370, 400, 480, 500]$$ Đây là các bước bạn cần thực hiện:
- Đặt vị trí $left = 1, right = 16$, từ đó ta có $mid = \left \lfloor \frac{left + right}{2} \right \rfloor = \left \lfloor \frac{1 + 16}{2} \right \rfloor = 8$. Cuốn sách tại vị trí này có số trang là $230 < 250$, ta đặt $left = 8 + 1 = 9$.
- $left = 9, right = 16$, từ đó ta có $mid = \left \lfloor \frac{left + right}{2} \right \rfloor = \left \lfloor \frac{9 + 16}{2} \right \rfloor = 12$. Cuốn sách tại vị trí này có số trang là $320 > 250$, ta đặt $right = 12 - 1 = 11$.
- $left = 9, right = 11$, từ đó ta có $mid = \left \lfloor \frac{left + right}{2} \right \rfloor = \left \lfloor \frac{9 + 11}{2} \right \rfloor = 10$. Cuốn sách tại vị trí này có số trang là $250> 250$, dừng tìm kiếm. Tại đây ta chỉ cần tìm từ vị trí thứ $10$ sang hai bên, dừng khi số trang của $1$ nhỏ hơn hoặc lớn hơn $250$.
int binary_search()
{
int n; // n is the right_most value
int left = 1, right = n; // assign the left_most and right_most values
while (left < right)
{
int mid = (left + right) / 2;
if (check(mid) > answer)
{
right = mid - 1;
}
else if (check(mid) < answer)
{
left = mid - 1;
}
else
{
return mid;
}
}
if (check(l) == answer) return l; // at this time l = r, if we haven't found the answer yet, check the final case
return -1; // or report that there are no answers.
}
Nhận xét
Đăng nhận xét