Hàm đánh giá trong tim kiếm nhị phân năm 2024
|
- title: Binary search (Tìm kiếm nhị phân a.k.a chặt nhị phân) - Binary search (Tìm kiếm nhị phân) === - ###### ✍️ Author: 2School Guideline ###### 📋 Content: [TOC] # Giới thiệu chung Tìm kiếm là một kĩ thuật vô cùng quan trọng để giải quyết các bài toán trong Tin học. Có nhiều phương pháp tìm kiếm được nghiên cứu, phát triển và ứng dụng; mỗi thuật toán đều có độ phức tạp và ưu/nhược điểm nhất định. Trong bài viết này, chúng mình sẽ tập trung đề cập đến một giải thuật tìm kiếm căn bản trong Khoa học máy tính - Binary Search (hay còn được biết đến là Tìm kiếm nhị phân hay chặt nhị phân). # Tìm kiếm phần tử trong mảng ## Bài toán 1. Cho mảng $a$ có $n$ phần tử và 1 số $x$ ($n ≤ 10^6, |a_i| ≤ 10^9, |x| ≤ 10^9$), xác định xem có phần tử $a_i = x$ trong mảng $a$ hay không, nếu tìm thấy in ra $“YES”$, không tìm thấy thì in ra $“NO”$ (giới hạn bài toán chỉ mang tính chất minh họa). 2. Cho mảng $a$ có $n$ phần tử **đã được sắp xếp tăng dần** và $q$ truy vấn, mỗi truy vấn là một số $x$ ($2 ≤ n ≤ 10^6, q ≤ 10^5, |a_i| ≤ 10^9, |x| ≤ 10^9$), với mỗi truy vấn, xác định xem có phần tử $a_i = x$ trong mảng $a$ hay không, nếu tìm thấy in ra $“YES”$, không tìm thấy thì in ra $“NO”$ (giới hạn bài toán chỉ mang tính chất minh họa). ## Tìm kiếm tuần tự kết quả (Linear Search) Một giải pháp cơ bản để giải các bài toán trên chính là duyệt qua tất cả các phần tử của mảng $a$ để tìm ra phần tử thỏa yêu cầu đề. ```cpp= void linearSearch(long long x){ //Quet qua tat ca phan tu trong mang for(int i = 1; i <= n; i++){ //Gia su chi so phan tu bat dau tu 1 //Tim thay phan tu thoa de => xuat ra "YES" va thoat ra khoi ham if(a[i] == x){ cout << "YES\n"; return; } } //Khong tim thay phan tu thoa de => xuat ra "NO" cout << "NO\n"; } ``` Ưu điểm của phương pháp này là dễ dàng suy ra từ đề bài, code ngắn gọn, cài đặt đơn giản. Ở bài toán $(1)$, các phần tử trong mảng được sắp xếp theo thứ tự ngẫu nhiên, do đó, Linear Search là phương pháp tốt nhất để tìm kiếm phần tử theo yêu cầu đề, do không có thêm dữ kiện nào về vị trí của $x$ trong mảng $a$. Trong tình huống xấu nhất, thuật toán buộc phải duyệt qua tất cả các phần tử trong mảng $a$, do đó, độ phức tạp của Linear Search là $O(n)$. Tuy nhiên, đối với bài toán $(2)$, ta phải lặp lại thao tác tìm kiếm này trong $q$ lần, dẫn đến số thao tác cần thực hiện tối đa là $n \cdot\ q$. Khi số bước lặp càng lớn ($n \cdot\ q \ge 10^7$), quá trình thực thi trở nên chậm hơn và có thể vượt quá giới hạn thời gian đề yêu cầu (thường là $1$ giây). Vì vậy, ta cần tìm một giải thuật tối ưu hơn để giải quyết bài toán $(2)$ trong thời gian hạn định. ## Tìm kiếm nhị phân (Binary Search) ### Cách 1 Để cải tiến thuật toán tìm kiếm, ta cần lưu ý một dữ kiện hết sức quan trọng trong đề bài $(2)$: **mảng $a$ đã được sắp xếp tăng dần**. Dựa vào thông tin trên, ta thiết lập được một thuật toán thu hẹp phạm vi tìm kiếm dựa trên giá trị của phần tử - Binary Search. Để hiểu hơn về cách giải thuật này hoạt động, ta xét ví dụ sau với $n = 9$, $a =\{3,5,8,13,18,19,21,27,32\}$, $q = 1$ và phần tử cần tìm trong truy vấn có giá trị $x = 13$. - Đặt $left$ là vị trí đầu bên trái, $right$ là vị trí đầu bên phải của vùng cần xét. Ví dụ: nếu bạn muốn tìm kiếm ở khu vực $[1, 9]$ thì $left = 1, right = 9$.  - Xét vị trí chính giữa của $a$ bằng công thức: $mid = \lfloor\frac{left + right}{2}\rfloor$, lúc này ta được giá trị của phần tử chính giữa là $a[mid] = 18$ - Do $a[mid] > x$ $(18 > 13)$ nên $a[mid...right] > x$ $\Rightarrow$ ta có thể loại bỏ đoạn $[mid...right]$ (trong trường hợp này là đoạn $[5, 9]$) và tiếp tục xét đoạn còn lại là $[left...mid - 1]$ (đoạn $[1, 4]$). - Khi này, ta có $mid = \lfloor\frac{left + right}{2}\rfloor = 2$ $\Rightarrow$ xét $a[2] = 5$.  - Vì $a[mid] < x$ nên $a[left...mid] < x \Rightarrow$ ta có thể lược đi đoạn $[left...mid]$ (đoạn $[1, 2]$) và tiếp tục xét đoạn $[mid + 1...right]$ (đoạn $[3, 4]$). - Lúc này, ta có $mid = \lfloor\frac{left + right}{2}\rfloor = 3 \Rightarrow$ xét $a[3] = 8$.  - Do $a[mid] < x$ nên ta có thể lược đi đoạn $[3, 3]$ và tiếp tục xét đoạn $[4, 4]$. - Lúc này, ta có $mid = \lfloor\frac{left + right}{2}\rfloor = 4$ $\Rightarrow$ xét $a[4] = 13$. Ta thấy được $a[4] = x$ $\Rightarrow$ có tồn tại phần tử $x$ ở vị trí $i = 4$ trong mảng $a$. Tổng quát lại các bước hoạt động:  Minh hoạ quá trình tìm kiếm phần tử $x$:  Bây giờ ta sẽ tiến hành cài đặt thuật toán dựa trên ý tưởng nêu trên. **Vòng lặp** ```cpp= void binarySearch(long long x) { //Dat bien trai, bien phai int left = 1, right = n; while(left <= right){ //Tim vi tri o giua int mid = (left + right) / 2; //Tim thay phan tu o vi tri mid if(a[mid] == x){ cout << "YES\n"; return; } //Phan tu o vi tri mid > x else if(a[mid] > x) right = mid - 1; //Phan tu o vi tri mid < x else left = mid + 1; } //Khong tim thay phan tu thoa de cout << "NO\n"; return; } ``` **Đệ quy** ```cpp= int binarySearch(int left, int right, long long x) { //Khong tim thay phan tu thoa de if(left > right) return -1; //Tim vi tri o giua int mid = (left + right) / 2; //Tim thay phan tu thoa de if(a[mid] == x) return 1; //Phan tu o vi tri mid > x else if(a[mid] > x) return binarySearch(left, mid - 1, x); //Phan tu o vi tri mid < x else return binarySearch(mid + 1, right, x); } int main(){ //nhap du lieu //duyet qua q truy van while(q){ long long x; cin >> x; if(binarySearch(1, n, x) != -1) cout << "YES\n"; else cout << "NO\n"; } } ``` - Phạm vi tìm kiếm khi khởi tạo là $[1...n]$, và sau mỗi bước, kích thước của vùng tìm kiếm này lại giảm đi một nửa, vì vậy, đối với mảng đã được sắp xếp theo thứ tự nhất định thì độ phức tạp của giải thuật là $O(\log{n})$. Cách cài đặt có hằng số tương đối nhỏ, tuy nhiên, nhược điểm của phương pháp cài này là đoạn code sẽ dài hơn các cách khác được giới thiệu bên dưới. - Ngoài ra, chúng ta cũng có thể tìm kiếm nhị phân trên mảng $a$ giảm dần, hay nói chung là một mảng **đã được sắp xếp**. Cách cài giống với tư tưởng trên thế nhưng chúng ta chỉ cần đổi điều kiện giảm dần phạm vi tìm kiếm. - Đối với giảm dần, ta chỉ cần thay điều kiện thành $a[mid] < x$ thì $right = mid - 1$ bởi chúng ta có thông tin rằng $a[mid...right] < x$ và trong trường hợp ngược lại ta bỏ đoạn $[left...mid]$ hay $left = mid + 1$ ### Cách 2 (mở rộng tham khảo) Khi giải các bài toán $(1)$ và $(2)$ bằng phương pháp Tìm kiếm tuần tự (Linear Search), ta cần "nhảy" lần lượt qua các phần tử trong mảng cho đến khi tìm được phần tử thỏa yêu cầu đề bài. Vì trong mỗi lượt, thao tác "nhảy" từ một phần tử đến phần tử kế cận được thực hiện $\Rightarrow$ độ dài "bước nhảy" là $1$. Để tối ưu giải thuật tìm kiếm nhằm giải quyết bài toán $(2)$, câu hỏi đặt ra là: làm thế nào để tăng độ dài "bước nhảy", giảm số thao tác "nhảy"? Dựa vào thông tin về tính có thứ tự của phần tử mảng $a$, ta sẽ thực hiện những bước nhảy có độ dài $\frac{n}{2}$, $\frac{n}{4}$, $\frac{n}{8}$,... và chậm dần tốc độ khi tiến càng gần đến mục tiêu tìm kiếm (giảm độ dài bước nhảy đến $\frac{n}{n} = 1$). Ý tưởng cài đặt Tìm kiếm nhị phân (Binary Search) này được giới thiệu trong cuốn sách [Competitive Programmer’s Handbook](https://cses.fi/book/book.pdf) của Antti Laaksonen. Xét một ví dụ: Cho $n = 9$, $a =\{3,5,8,13,18,19,21,27,32\}$, $q = 1$ và phần tử cần tìm trong truy vấn có giá trị $x = 27$.  Quan sát hình ta thấy, từ vị trí $i = 1$, để đến được vị trí của phần tử có giá trị bằng $x$ cần tìm, ta thực hiện "nhảy" lần lượt 1 bước có độ dài $\frac{n}{2}$, 1 bước có độ dài $\frac{n}{4}$ và 1 bước có độ dài là $\frac{n}{8} = 1$. Thuật toán được cài đặt như sau: ```cpp= void binarySearch(long long x){ //Vi tri bat dau nhay int k = 1; //Thuc hien cac buoc nhay for(int b = n / 2; b >= 1; b /= 2){ while((k + b <= n) && (a[k + b] <= x)) k += b; } //Kiem tra phan tu co thoa de if(a[k] == x){ cout << "YES\n"; } else cout << "NO\n"; } ``` Chúng ta cùng xem cách giải thuật hoạt động với ví dụ trên. - Đoạn code thực hiện $2$ lần "nhảy thử" với độ dài "bước nhảy" là $\frac{n}{2}$. Ở lần "nhảy thử" thứ $2$, $a[k + b] > x$ (tương ứng $32 > 27$) $\Rightarrow$ thoát khỏi vòng lặp while, chuyển đến lần lặp tiếp theo của vòng for.  - Đoạn code tiếp tục thực hiện $2$ lần "nhảy thử" với độ dài "bước nhảy" là $\frac{n}{4}$. Ở lần "nhảy thử" thứ $2$, $a[k + b] > x$ (tương ứng $32 > 27$) $\Rightarrow$ thoát khỏi vòng lặp while, chuyển đến lần lặp tiếp theo của vòng for.  - Đoạn code tiếp tục thực hiện $2$ lần "nhảy thử" với độ dài "bước nhảy" là $\frac{n}{8} = 1$. Ở lần "nhảy thử" thứ $2$, $a[k + b] > x$ (tương ứng $32 > 27$) => thoát khỏi vòng lặp while. Trong lần lặp tiếp theo của vòng lặp for, $\lfloor\frac{b}{2}\rfloor$ $=$ $\lfloor\frac{1}{2}\rfloor$ $= 0$ $\Rightarrow$ thoát khỏi vòng lặp for.  - Lúc này, $k = \frac{n}{2} + \frac{n}{4} + \frac{n}{8} = 1 + 4 + 2 + 1 = 8$. Nhận thấy, $a[8] = 27 = x$ $\Rightarrow$ Tồn tại phần tử thỏa đề $\Rightarrow$ Xuất ra $"YES"$. Tổng quát lại các bước hoạt động:  Ta có thể chứng minh được, ở mỗi bước, đoạn code trong vòng lặp for sẽ được thực hiện tối đa $2$ lần (trung bình là $1$ lần), và thao tác "nhảy thử" được thực hiện từ $1 - 3$ lần. Với vòng lặp for, độ dài "bước nhảy" $b$ sẽ được giảm đi một nửa sau mỗi lần lặp. Vì vậy, độ phức tạp thuật toán là $O(\log{n})$. Ưu điểm của cách này là code vô cùng ngắn gọn và thuận theo dòng suy nghĩ khi cài đặt. Tuy vậy, việc "nhảy thử" từ $1 - 3$ lần ở mỗi bước sẽ là một vấn đề khi bạn dùng cách cài đặt này cho các bài toán có giới hạn chặt, các bài **interactive** (bài toán mà chương trình tương tác trực tiếp với trình chấm) dùng đến Binary Search. Để giải được các bài toán sử dụng Tìm kiếm nhị phân (Binary Search) trong các kì thi, bạn chỉ cần cài đặt thành thạo $1$ trong $2$ cách nêu trên. Tuy nhiên, cách bạn mô phỏng một thuật toán sẽ định hướng tư duy của bạn về thuật toán đó. Việc tìm hiểu đa dạng các cách xây dựng chương trình cho một giải thuật giúp việc nhận biết thuật toán đó trong một bài toán trở nên dễ dàng và thuận lợi hơn. Do đó, chúng mình khuyến khích bạn đọc và hiểu cả hai cách cài Binary Search được giới thiệu ở trên. ### Các hàm tìm kiếm có sẵn trong ngôn ngữ C++ Thư viện chuẩn C++ cũng cung cấp cho lập trình viên các hàm có sẵn để thực hiện tìm kiếm bằng Binary Search. Trong nhiều trường hợp, việc sử dụng chương trình con và thủ tục được cài đặt sẵn trong ngôn ngữ lập trình làm cho code của bạn được ngắn gọn hơn, tốc độ thực thi cũng nhanh hơn (do các hàm sẵn có thường có hằng số tương đối nhỏ). Sau đây, chúng mình sẽ giới thiệu đến bạn một số hàm Tìm kiếm nhị phân phổ biến trong ngôn ngữ C++ có thể sử dụng để giải quyết bài toán $(2)$. #### Hàm binary_search() - **Công dụng:** Hàm ```binary_search()``` trong C++ được sử dụng trên mảng đã sắp xếp để trả về **true** nếu tồn tại $x$ trong mảng chứa, và trả về **false** nếu không tìm thấy. - **Cách khai báo:** ```binary_search({first}, {last}, {x});``` Trong đó: - **first, last** lần lượt là 2 con trỏ trỏ đến vị trí xuất phát và kết thúc của dãy cần tìm kiếm. Khoảng được tìm kiếm là **[first, last)**, tức là tất cả các phần tử giữa first và last và thêm phần tử được trỏ bởi first nhưng không có phần tử trỏ bởi last, nếu tất cả phần tử trong khoảng tìm kiếm đều bé hơn **x** thì hàm sẽ trả về **last**. - **x** là giá trị cần được tìm kiếm. **Code minh họa bài toán (2)** ```cpp= int main(){ //nhap du lieu //duyet qua q truy van while(q--){ long long x; cin >> x; //Tim thay phan tu thoa de if(binary_search(a + 1, a + n + 1, x)) cout << "YES\n"; //Khong tim thay phan tu thoa de else cout << "NO\n"; } } ``` #### Hàm equal_range() - **Công dụng:** Hàm ```equal_range()``` trong C++ được sử dụng trên mảng đã sắp xếp để trả về một **pair** gồm 2 con trỏ: con trỏ đầu tiên trỏ tới vị trí đầu tiên có giá trị **lớn hơn hoặc bằng** $x$, con trỏ thứ hai trỏ tới vị trí đầu tiên có giá trị **lớn hơn** $x$. Tận dụng điều này để giải bài toán $(2)$, ta kiểm tra xem đoạn con gồm các phần tử có giá trị bằng $x$ có độ dài lớn hơn $0$ hay không. Nếu độ dài đoạn con tìm được lớn hơn $0$ $\Rightarrow$ trong mảng tồn tại phần tử có giá trị bằng $x$ $\Rightarrow$ xuất ra $"YES"$, ngược lại thì in ra $"NO"$. - **Cách khai báo:** ```equal_range({first}, {last}, {x});``` Trong đó: - **first, last** lần lượt là $2$ con trỏ trỏ đến vị trí xuất phát và kết thúc của dãy cần tìm kiếm. Khoảng được tìm kiếm là **[first, last)**, tức là tất cả các phần tử giữa first và last và thêm phần tử được trỏ bởi first nhưng không có phần tử trỏ bởi last, nếu tất cả phần tử trong khoảng tìm kiếm đều bé hơn $x$ thì hàm sẽ trả về **last**. - $x$ là giá trị cần được tìm kiếm. **Code minh họa bài toán $(2)$** (Từ khóa auto sẽ được giải thích ở phần tiếp theo) **Mảng thường** ```cpp= int main(){ //nhap du lieu //duyet qua q truy van while(q--){ long long x; cin >> x; //Khai bao pair gom 2 con tro auto r = equal_range(a + 1, a + n + 1, x); //Do dai doan con co cac phan tu bang x int ln = r.second - r.first; //Ton tai phan tu bang x if(ln > 0) cout << "YES\n"; //Khong ton tai phan tu bang x else cout << "NO\n"; } } ``` **Vector** ```cpp= vector include
|
