Chiến lược tìm kiếm chia để trị

Chúng ta đã biết rằng các thuật toán tìm kiếm được chia làm hai loại lớn.

• Tìm kiếm vét cạn (brute-force search): Được triển khai bằng cách duyệt qua cấu trúc dữ liệu, với độ phức tạp thời gian là \(O(n)\).
• Tìm kiếm thích ứng (adaptive search): Tận dụng cách tổ chức dữ liệu cụ thể hoặc thông tin có trước, với độ phức tạp thời gian đạt tới \(O(\log n)\) hoặc thậm chí là \(O(1)\).

Trên thực tế, các thuật toán tìm kiếm có độ phức tạp thời gian là \(O(\log n)\) thường được triển khai dựa trên chiến lược chia để trị, chẳng hạn như tìm kiếm nhị phân và các cấu trúc dạng cây.

• Mỗi bước của tìm kiếm nhị phân (binary search) chia bài toán (tìm kiếm phần tử mục tiêu trong mảng) thành bài toán nhỏ hơn (tìm kiếm phần tử mục tiêu trong một nửa mảng), tiếp tục như vậy cho đến khi mảng trống hoặc tìm thấy phần tử mục tiêu.
• Cây là cấu trúc đại diện cho ý tưởng chia để trị. Trong các cấu trúc dữ liệu như cây tìm kiếm nhị phân, cây AVL và đống, độ phức tạp thời gian của các thao tác khác nhau là \(O(\log n)\).

Chiến lược chia để trị của tìm kiếm nhị phân như sau.

• Bài toán có thể phân rã: Tìm kiếm nhị phân phân rã bài toán ban đầu (tìm kiếm trong mảng) thành các bài toán con (tìm kiếm trong một nửa mảng) một cách đệ quy, bằng cách so sánh phần tử ở giữa với phần tử mục tiêu.
• Các bài toán con là độc lập: Trong tìm kiếm nhị phân, mỗi vòng chỉ xử lý một bài toán con, bài toán này không bị ảnh hưởng bởi các bài toán con khác.
• Lời giải của các bài toán con không cần hợp nhất: Tìm kiếm nhị phân nhằm mục đích tìm kiếm một phần tử cụ thể, do đó không cần hợp nhất lời giải của các bài toán con. Khi một bài toán con được giải quyết, bài toán ban đầu cũng được giải quyết.

Chia để trị có thể nâng cao hiệu suất tìm kiếm vì tìm kiếm vét cạn chỉ có thể loại bỏ một lựa chọn trong mỗi vòng, trong khi tìm kiếm chia để trị có thể loại bỏ một nửa số lựa chọn trong mỗi vòng.

Triển khai tìm kiếm nhị phân dựa trên chia để trị

Trong các phần trước, tìm kiếm nhị phân được triển khai dựa trên vòng lặp (iteration). Bây giờ chúng ta sẽ triển khai nó dựa trên chia để trị (đệ quy).

Question

Cho một mảng đã sắp xếp (sorted array) nums có độ dài \(n\) gồm các phần tử độc nhất, hãy tìm target.

Dưới góc nhìn của chia để trị, chúng ta ký hiệu bài toán con tương ứng với khoảng tìm kiếm \([i, j]\) là \(f(i, j)\).

Bắt đầu từ bài toán ban đầu \(f(0, n-1)\), thực hiện tìm kiếm nhị phân qua các bước sau.

1. Tính trung điểm (midpoint) \(m\) của khoảng tìm kiếm \([i, j]\), và sử dụng nó để loại bỏ một nửa khoảng tìm kiếm.
2. Giải quyết bài toán con có kích thước giảm đi một nửa một cách đệ quy, bài toán đó có thể là \(f(i, m-1)\) hoặc \(f(m+1, j)\).
3. Lặp lại các bước 1. và 2. cho đến khi tìm thấy mục tiêu (target), hoặc trả về kết quả khi khoảng tìm kiếm trống.

Hình bên dưới thể hiện quá trình chia để trị của tìm kiếm nhị phân để tìm phần tử \(6\) trong một mảng.

Trong mã triển khai, chúng ta khai báo một hàm đệ quy (recursive function) dfs() để giải quyết bài toán \(f(i, j)\):

[file]{binary_search_recur}-[class]{}-[func]{binary_search}