Google Search, Bing… là những công cụ tìm kiếm đã quá đỗi quen thuộc với chúng ta, và gần đây nhất, ChatGPT, 1 sản phẩm của OpenAI, được ‘hậu thuẫn’ bởi gã khổng lồ công nghệ Microsoft, đã gây ra 1 cơn bão làm náo loạn giới công nghệ, với việc xử lý rất nhanh những truy vấn tìm kiếm về một thông tin bất kỳ nào đó và có thể đưa ra những kết quả gần như chính xác. Tuy vẫn còn tồn tại nhiều sai sót nhưng những gì ChatGPT có thể làm được đã vượt xa trí tưởng tượng phức tạp nhất của con người và đồng thời, thực hiện cuộc cách mạng hóa cải tổ công cụ tìm kiếm nhanh, mạnh hơn nữa. ‘Tìm kiếm’ quả là một điều thú vị và trong bài học số 4 của lớp CS101, chúng ta sẽ cùng nhau tìm hiểu về hai giải thuật tìm kiếm cơ bản và phổ biến nhất, có ứng dụng rất nhiều trong đời sống hiện nay, đó là ‘Tìm kiếm tuần tự’ và ‘Tìm kiếm nhị phân’.
1. Tìm kiếm tuần tự (Linear Search)
Tìm kiếm tuần tự (Linear Search) là một thuật toán cơ bản và gần như chúng ta có thể thực hiện ngay như một bản năng sẵn có. Giả sử như chúng ta có một dãy các hộp gỗ đóng kín xếp cạnh nhau, mỗi hộp được đánh dấu thứ tự từ 0 đến 88 và trong mỗi hộp có 1 số tự nhiên bất kỳ:
70, 40, 30, 11, 7, 41, 25, 14, 52
Yêu cầu bài toán được đặt ra: Số 41 ở trong chiếc hộp thứ mấy? Bởi ta không biết số 41 nằm ở đâu trong mỗi hộp được đóng kín nên ta phải kiểm tra từng hộp, bằng cách mở chúng lần lượt từ trái sang phải. Nếu mở tới hộp có số thứ tự 5, thấy được số 41 nằm trong đó nên ta kết luận, số 41 nằm ở thứ tự 5. Đó cũng là cách hoạt động của thuật toán Tìm kiếm tuần tự. Bằng cách duyệt qua từng phần tử từ trái qua phải, ta có thể kết luận xem liệu phần tử cần tìm kiếm có tồn tại trong dãy trong dãy hay không, và nếu có, trả kết quả là vị trí của phần tử cần tìm nằm ở đâu trong dãy (thứ tự). Dưới đây là hình vẽ mô phỏng từng bước của thuật toán tìm kiếm tuần tự.
Đó là cách hoạt động của thuật toán Tìm kiếm tuần tự và cách tiếp cận của thuật toán này vô cùng đơn giản. Tuy vậy, giả sử như có 100,000 chiếc hộp và chúng ta được yêu cầu phải tìm hộp có chứa số 41 trong đó, liệu Tìm kiếm tuần tự có phải một giải pháp hiệu quả?
2. Tìm kiếm nhị phân (Binary Search)
Để giải quyết những bài toán tìm kiếm với số lượng lớn như vậy, chúng ta sẽ cùng tìm hiểu 1 thuật toán tìm kiếm kinh điển khác sẽ rút gọn thời gian thực hiện tìm kiếm hơn rất nhiều. Đó là thuật toán ‘Tìm kiếm nhị phân’ (Binary Search).
Chúng ta tiếp tục ví dụ về những chiếc hộp với mỗi chiếc đều được đánh số. Chỉ duy nhất một chiếc hộp có chứa kho báu ở trong và bạn được phép biết số của chiếc hộp đó. Tuy nhiên, những chiếc hộp được xếp ngẫu nhiên và số lượng chiếc hộp lên tới hàng trăm chiếc, liệu bạn có kiểm tra từng hộp, rồi so sánh chúng với số của chiếc hộp có chứa kho báu mà bạn đang cầm? Kiểm tra từng hộp cũng là một phương án, nhưng chúng ta mất quá nhiều thời gian trong việc kiểm tra từng chiếc khi số lượng chiếc hộp quá lớn như vậy, do đó, thuật toán tìm kiếm nhị phân sẽ được áp dụng trong ví dụ như sau.
Giả sử những chiếc hộp được sắp xếp theo thứ tự từ nhỏ tới lớn với các số được đánh dấu trên mỗi chiếc hộp. Tiếp theo, bắt đầu với chiếc hộp ở giữa, và ta so sánh số trên chiếc hộp ở giữa này với số của hộp kho báu mà ta đang có. Lưu ý rằng, khi đã sắp xếp những chiếc hộp theo thứ tự như trên, các hộp với số nhỏ hơn sẽ xếp trước và các hộp với số lớn sẽ xếp sau. Các hộp được sắp xếp theo thứ tự các số trong hộp là điều kiện quan trọng của thuật toán tìm kiếm nhị phân.
Khi so sánh số của chiếc hộp ở giữa với số của hộp kho báu, ta nhận ra và có thể chắc chắn một điều rằng: nếu như số của chiếc hộp ở giữa lớn hơn số của chiếc hộp kho báu, vậy thì chiếc hộp kho báu chỉ có thể nằm trong khoảng từ vị trí chiếc hộp đầu tiên, cho tới vị trí trước chiếc hộp ở giữa, bởi lẽ, ta đã sắp xếp những chiếc hộp theo thứ tự các số trên hộp từ nhỏ tới lớn.
Ví dụ nếu như chiếc hộp ở giữa mang số 60, mà chiếc hộp có chứa kho báu mà ta cần tìm mang số 35, ta có thể biết được, chiếc hộp 35 phải nằm trước chiếc hộp 60 (bởi ta đã sắp xếp trước khi tìm kiếm)
Ngược lại, nếu như chiếc hộp ở giữa mang số 60, nhưng chiếc hộp có chứa kho báu cần tìm mang số 72, ta chắc chắn chiếc hộp có chứa kho báu sẽ nằm đâu đó sau chiếc hộp số 60, và ta sẽ loại bỏ, không cần tìm những hộp mang số nhỏ hơn 60 nữa. Như vậy việc tìm kiếm sẽ nhanh hơn rất nhiều.
Lặp đi lặp lại quá trình như vậy, với việc so sánh số dán trên chiếc hộp ở giữa với số của hộp kho báu cần tìm, ta có thể thu hẹp được xuống một hộp duy nhất và đó cũng là đáp án.
Dưới đây là mô phỏng thuật toán tìm kiếm nhị phân theo từng bước.
Cho 1 mảng A như trong hình với các phần tử đã được sắp xếp theo thứ tự tăng dần, từ nhỏ tới lớn.
Yêu cầu được đặt ra, chúng ta phải tìm kiếm phần tử có giá trị 55 nằm ở đâu trong dãy, nếu có, trả về vị trí của phần tử cần tìm, ngược lại, trả về “Không tìm thấy”
(Ký hiệu của mảng là A)
Ở lượt tìm kiếm đầu tiên, ta chọn phần tử ở giữa của dãy, tức vị trí số 6. Giá trị của phần tử ở vị trí số 6 là 41 (A[6] = 41). Vì các phần tử trong mảng đã được sắp xếp theo thứ tự tăng dần, do đó, ta có thể suy luận rằng, phần tử chúng ta cần tìm, 55, chắc chắn sẽ nằm trong phạm vi tìm kiếm từ phần tử thứ 7 trở về sau (những phần tử lớn hơn 41). Vì vậy, khoảng không gian tìm kiếm của chúng ta sẽ giảm xuống còn 1 nữa (từ 7 -> 11, lượt 2)
Tiếp tục chọn phần tử ở giữa trong khoảng không gian tìm kiếm, lần này là phần từ ở vị trí thứ 8. Phần từ ở vị trí thứ 8 là 72, vì vậy, ta biết chắc chắn phần từ 55 sẽ nằm phía trước phần tử này, do đó, ta có thể thu hẹp phạm vi tìm kiếm thêm 1 lần nữa (từ vị trí thứ 7 đến vị trí thứ 8).
Ở lượt tìm cuối cùng, ta cũng xét phần tử ở giữa của không gian tìm kiếm hiện tại ở vị trí 7 (ở đây số lượng phần tử của không gian tìm kiếm là chẵn, do đó có hai phần tử giữa, ta có thể chọn một trong hai đều được, ở ví dụ này ta chọn phần tử giữa đầu tiên), Nhận thấy A[7]=55, bằng số chúng ta cần tìm, ta kết luận 5 chính là vị trí của phần tử cần tìm và dừng thuật toán.
Một lưu ý vô cùng quan trọng sau các bước cụ thể ở trên, với việc thu hẹp khoảng tìm kiếm dựa trên việc so sánh phần tử ở giữa với phần tử cần tìm, thuật toán tìm kiếm nhị phân chỉ có thể áp dụng khi dãy đã được sắp xếp sẵn, với giá trị của các phần tử có thể theo thứ tự tăng dần hoặc thứ tự giảm dần.
Chúng ta có thể hình dung thuật toán tìm kiếm nhị phân bằng hình ảnh sinh động sau:
Ngoài ra thuật toán tìm kiếm nhị phân còn có thể được sử dụng để tìm kiếm trong đời sống hàng ngày với nhiều loại dữ liệu khác nhau (số, chữ,…). Một ứng dụng là tìm tên trong danh bạ điện thoại vì các tên đã được sắp xếp theo thứ tự bảng chữ cái. Một ứng dụng khác là khi chúng ta cần tìm một từ trong từ điển. Các bạn học sinh có ví dụ nào về tìm kiếm nhị phân thì có thể chia sẻ trên STEAMese Profile nhé. Ngoài hai thuật toán tìm kiếm tuần tự và nhị phân, chúng ta còn rất nhiều thuật toán tìm kiếm khác. Các bạn học sinh cùng tìm hiểu và chia sẻ trên STEAMese Profile nhé.
— — —
STEAM for Vietnam Foundation là tổ chức phi lợi nhuận 501(c)(3) được thành lập tại Hoa Kỳ với sứ mệnh thúc đẩy các hoạt động liên quan tới giáo dục STEAM (Science — Khoa học, Technology — Công nghệ, Engineering — Kỹ thuật, Arts — Nghệ thuật, Mathematics — Toán học) tại Việt nam. STEAM for Vietnam được thành lập và vận hành bởi đội ngũ tình nguyện viên là du học sinh và chuyên gia người Việt trên khắp thế giới.