chuyenhalong.ucode.vn cung cấp các khóa học lập trình tương tác với Python, Scratch, C/C++, Pascal, Game, Thuật toán, Web, Ứng dụng di động… cho tất cả mọi lứa tuổi, từ học sinh tiểu học đến người đi làm. Các khóa học được biên soạn bởi các chuyên gia giàu kinh nghiệm với những video, bài giảng tương tác, bài tập trực quan và những dự án thực tế. Tất cả đều được thực hiện ngay trên trình duyệt web của bạn.

- title Tìm kiếm nhị phân (Binary search) - Tìm kiếm nhị phân (Binary search) === - ###### ✍️ 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 (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 không giảm** (với mọi $i$ sao cho $1 ≤ i < n$, $a_i ≤ a_{i + 1}$) 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) { //Quét qua tất cả phần tử trong mảng for (int i = 1; i <= n; i) { //Giả sử chỉ số phần tử bắt đầu từ 1 //Tìm thấy phần tử thỏa đề => Xuất ra "YES" và thoát ra khỏi hàm if (a[i] == x) { cout << "YES\n"; return; } } //Không tìm thấy phần tử thỏa đề => Xuât 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 không giảm**. 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ử. Để 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) { //Đặt biến trái và biến phải int left = 1, right = n; while (left <= right) { //Tìm vị trí ở giữa int mid = (left + right) / 2; //Tìm thấy phần tử ở vị trí mid if (a[mid] == x) { cout << "YES\n"; return; } //Phần tử ở vị trí mid > x else if(a[mid] > x) right = mid - 1; //Phần tử ở vị trí mid < x else left = mid + 1; } //Không tìm thấy phần tử thỏa đề cout << "NO\n"; return; } ``` **Đệ quy** ```cpp= int binarySearch(int left, int right, long long x) { //Không tìm thấy phần tử thỏa đề if(left > right) return -1; //Tìm vị trí ở giữa int mid = (left + right) / 2; //Tìm thấy phần tử thỏa đề if(a[mid] == x) return 1; //Phần tử ở vị trí mid > x else if(a[mid] > x) return binarySearch(left, mid - 1, x); //Phần tử ở vị trí mid < x return binarySearch(mid + 1, right, x); } int main() { //Nhập dữ liệu //Duyệt qua q truy vấn 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$ không tăng, 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 không tăng và phạm vi tìm kiếm. - Đối với mảng không tăng, 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](//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) { //Vị trí bắt đầu nhảy int k = 1; //Thực hiện các bước nhảy for (int b = n / 2; b >= 1; b /= 2) { while ((k + b <= n) && (a[k + b] <= x)) k += b; } //Kiểm tra phần tử có thỏa đề 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. :::spoiler **Chứng minh tham khảo** Ta có: $\lfloor\frac{x}{2}\rfloor * 3 > x \ge \lfloor\frac{x}{2}\rfloor * 2$. Do đó, với $b = \lfloor\frac{x}{2}\rfloor * 3$, điều kiện $a[k + b] \le x$, không còn đúng, dẫn đến việc thoát ra khỏi vòng lặp $while$. ::: 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() { //Nhập dữ liệu //Duyệt qua q truy vấn while (q--) { long long x; cin >> x; //Tìm thấy phần tử thỏa đề if (binary_search(a + 1, a + n + 1, x)) cout << "YES\n"; //Không tìm thấy phần tử thỏa đề 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)$** **Mảng thường** ```cpp= int main() { //Nhập dữ liệu //Duyệt qua q truy vấn while (q--) { long long x; cin >> x; //Khai báo pair gồm hai con trỏ auto r = equal_range(a + 1, a + n + 1, x); //Độ dài đoạn con có phần tử bằng x int ln = r.second - r.first; //Tồn tại phần tử bằng x if (ln > 0) cout << "YES\n"; //Không tồn tại phần tử bằng x else cout << "NO\n"; } } ``` **Vector** ```cpp= vector<long long> a; int main() { //Nhập dữ liệu //duyệt qua q truy vấn while (q--) { long long x; cin >> x; //Khai báo pair gồm hai con trỏ auto r = equal_range(a.begin(), a.end(), x); //Độ dài đoạn con có phần tử bằng x int ln = r.second - r.first; //Tồn tại phần tử bằng x if(ln > 0) cout << "YES\n"; //Không tồn tại phần tử bằng x else cout << "NO\n"; } } ``` # Tìm phần tử trong mảng có giá trị gần nhất với một số x Chúng ta đã thấy sự tiện lợi lớn của thuật toán Tìm kiếm nhị phân khi đã giúp cải thiện rất nhiều tốc độ của bài toán **tìm kiếm phần tử trong mảng đã được sắp xếp**. Không dừng lại ở đó, Binary Search vẫn còn nhiều những phương hướng áp dụng thú vị khác trong giải quyết các vấn đề Tin học. Chúng ta hãy cùng xem qua một ứng dụng phổ biến của Binary Search trong lập trình - tìm phần tử trong mảng có giá trị gần nhất với số $x$. ## Bài toán tìm phần tử gần nhất bé hơn hoặc bằng - Cho mảng $a$ có $n$ phần tử được đánh số từ $1 \rightarrow n$ **đã được sắp xếp tăng dần** và $1$ số nguyên $x$, xác định vị trí lớn nhất của phần tử bé hơn hoặc bằng $x$. Nếu không có phần tử nào bé hơn $x$, xuất $-1$ $(n ≤ 10^6, |a_i| ≤ 10^9, |x| ≤ 10^9)$. - Ví dụ: $a = [3,5,10,11,13, 18,18,25,27,31], x = 20$ có kết quả là $7$ $(a[7] = 18)$. ### Lời giải - Đầu tiên chúng ta sẽ cài đặt lại thuật toán nhị phân, với hai biên $left$ và $right$, cùng phần tử trung vị $mid = \lfloor\frac{left + right}{2}\rfloor$ - Đặt biến $ans$ để lưu kết quả mỗi lần $a[mid] \le x$ thì $mid$ đó sẽ là $1$ đáp án hợp lệ, hay $ans = mid$. Sau đó bỏ qua toàn bộ đoạn $l \rightarrow mid$ bởi vì ta biết rằng trong đoạn này đáp án $mid$ là tối ưu nhất, ta sẽ đi kiểm tra đoạn $[mid + 1, r]$, hay ta đặt $l = mid + 1$. Còn ngược lại nếu $a[mid] > x$, thì ta biết rằng tất cả các giá trị $a[mid \rightarrow r] > x$ (không hợp lệ), thế nên ta đặt $r = mid - 1$ để bỏ qua đoạn $mid \rightarrow r$. - Nếu không tìm được giá trị nào bé hơn hoặc bằng $x$ sau khi $2$ biên $left$ và $right$ chạm nhau thì ta xuất ra $-1$. **Code:** ```cpp int binarySearch (int x) { int left = 1, right = n; // Đặt vùng biên trái và biên phải cần xét int ans = -1; // khai báo biến ans để lưu trữ kết quả, nếu không tìm thấy thì mặc định là -1 while (left <= right) { int mid = (left + right) / 2; // Tìm vị trí ở giữa if (a[mid] <= x) { ans = mid; //lưu trữ kết quả left = mid + 1; // Nếu a[mid] <= x thì ta bỏ qua đoạn l -> mid và ghi nhận mid là 1 kết quả hợp lệ } else right = mid - 1; // Nếu a[mid] > x thì bỏ qua đoạn mid -> r } // Trả về vị trí lớn nhất có giá trị <= x return ans; } ``` ## Bài toán tìm phần tử gần nhất lớn hơn hoặc bằng - Qua cách xử lí của bài toán trên, chúng ta cũng có thể biến đổi bài toán thành tìm kiếm phần tử lớn hơn gần nhất với phần tử $x$ cho trước bằng cách thay đổi điều kiện. **Code:** ```cpp int binarySearch(int x) { int left = 1, right = n; // Đặt vùng biên trái và biên phải cần xét int ans = -1; // khai báo biến ans để lưu trữ kết quả, nếu không tìm thấy thì mặc định là -1 while (left <= right) { int mid = (left + right) / 2; // Tìm vị trí ở giữa if (a[mid] >= x) { ans = mid; //lưu trữ kết quả right = mid - 1; // Nếu a[mid] >= x thì ta bỏ qua đoạn mid -> r và ghi nhận mid là 1 kết quả hợp lệ } else left = mid + 1; // Nếu a[mid] < x thì bỏ qua đoạn l -> mid } // Trả về vị trí lớn nhất có giá trị >= x return ans; } ``` - Độ phức tạp của phương pháp giải cho $2$ bài toán trên là: $O(\log{n})$ (với mảng $a$ đã được sắp xếp) - Minh hoạ quá trình tìm vị trí lớn nhất của phần tử $\le x$ trong mảng:  ## Sử dụng hàm có sẵn - Bên cạnh đó, để giải quyết những bài toán trên, 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 như `lower_bound()` và `upper_bound()`. Việc sử dụng các hàm này sẽ giúp code của bạn ngắn gọn hơn, tiết kiệm thời gian cài đặt. - Trong bài viết có đề cập tới khái niệm con trỏ và iterator, để tránh vượt quá giới hạn bài viết, bạn đọc có thể đọc về 2 khái niệm này tại đây: [con trỏ trong mảng 1 chiều](//cpp.daynhauhoc.com/8/2-con-tr-va-mang-mot-chieu/), [iterator](//cpp.daynhauhoc.com/11/2-stl-iterators/) ### Hàm lower_bound() - **Công dụng:** Hàm `lower_bound()` trong C++ được sử dụng trên mảng đã sắp xếp để trả về một iterator trỏ đến phần tử đầu tiên có giá trị không nhỏ hơn $x$ trong phạm vi vùng biên trái đến trước vùng biên phải mà ta khai báo cho hàm. - **Cách khai báo:** - ```lower_bound({first}, {last}, {x});``` đối với mảng thường và vector - **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:** ```cpp=

include <bits/stdc++.h> using namespace std; int main() { int a[] = {1, 2, 4, 4, 6, 9, 10}; // Khai báo mảng a auto ans = lower_bound(a, a + 7, 4); // lưu lại kết quả của hàm lower_bound vào biến pos cout << "Vi tri dau tien khong nho hon 4 la " << ans - a << endl; // Kết quả sẽ là hiệu của con trỏ ans và con trỏ mảng a // Kết quả là 2 (do a[2] == 4) return 0; } ``` ### Hàm upper_bound() - **Công dụng:** Hàm `upper_bound()` trong C++ được sử dụng trên mảng đã được sắp xếp, với công dụng trả về iterator trỏ đến phần tử đầu tiên có giá trị lớn hơn $x$ trong phạm vi giữa 2 vùng biên tới trước vùng biên phải mà ta đã khai báo cho hàm. - **Cách khai báo:** ```upper_bound({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:** ```cpp=

include<bits/stdc++.h> using namespace std; int main() { int a[] = {0, 2, 4, 4, 6, 9, 10}; // Khai báo mảng a auto pos = upper_bound(a, a + 7, 4); // lưu lại kết quả của hàm upper_bound vào biến pos cout << "Vi tri dau tien lon hon 4 la " << pos - a << endl; // Kết quả sẽ là hiệu của con trỏ ans và con trỏ mảng a // Kết quả là 4 (do a[4] == 6) return 0; } ``` ### Mở rộng 1. Dựa vào tính chất của `upper_bound()` ta thấy được có thể sử dụng hàm trên như sau: - Khi sử dụng hàm `upper_bound()` trên mảng $a$, lưu kết quả của hàm vào iterator $p$, nếu $p$ trả về khác iterator trỏ tới phần tử đầu tiên của mảng (hay khác $a.begin()$ của $vector$) (do khi đó sẽ không có phần tử nào của mảng $\le x$), thì `--p`(hay con trỏ chỉ tới phần tử trước phần tử $> x$) sẽ trỏ về phần tử có vị trí lớn nhất mà giá trị $\le x$ cần tìm. - Tương tự như vậy khi với `lower_bound()`, nếu iterator $p$ khác iterator trỏ tới phần tử đầu tiên của mảng, thì `--p`(hay con trỏ chỉ tới phần tử trước phần tử $\ge x$) sẽ trỏ về phần tử có vị trí lớn nhất mà giá trị $< x$ cần tìm. **Code minh họa:** ```cpp=

include <bits/stdc++.h> using namespace std; int main() { int a[] = { 9, 8, 2, 6, 15, 3, 1 }; // Khai báo mảng a sort(a, a + 7); // Dùng hàm sort để sắp xếp lại mảng // Mảng a lúc này: 1, 2, 3, 6, 8, 9, 15 // Tìm vị trí lớn nhất của phần tử có giá trị bé hơn hoặc bằng với x auto p1 = upper_bound(a, a + 7, 8); // Lưu kết quả của upper_bound vào biến p1 if (p1 != a) cout << (--p1) - a << endl; // Xuất ra vị trí lớn nhất của phần tử có giá trị bé hơn hoặc bằng với x else cout << -1 << endl; // Nếu không có phần tử nào trong mảng <= x thì ta xuất -1 với ý nghĩa là không tìm thấy // Kết quả khi này sẽ là 4 (a[4] = 8) // Tìm vị trí lớn nhất của phần tử có giá trị bé hơn x auto p2 = lower_bound(a, a + 7, 8); // Lưu kết quả của lower_bound vào biến p2 if (p1 != a) cout << (--p1) - a << endl; // Xuất ra vị trí lớn nhất của phần tử có giá trị bé hơn x else cout << -1 << endl; // Nếu không có phần tử nào trong mảng < x thì ta xuất -1 với ý nghĩa là không tìm thấy // Kết quả khi này sẽ là 3 (a[3] = 6) } ``` - Từ khóa `auto` được dùng để tự động nhận dạng kiểu dữ liệu thông qua kiểu dữ liệu của giá trị khởi tạo ra nó. (Trong đoạn code trên, ta có thể khai báo `auto p1 = upper_bound(a, a + 7, 8);` thay vì `int *p1 = upper_bound(a,a+7,8);`) 2. Chúng ta cũng có thể kết hợp sử dụng ```set```, ```multiset``` với hai hàm ```upper_bound()``` và ```lower_bound()``` với cú pháp như sau: ```<set_name>.lower_bound(x)``` Trong đó: - <set_name>: là tên của ```set```, ```multiset``` - x : là giá trị cần tìm kiếm - Nếu muốn sử dụng hàm ```upper_bound()``` ta chỉ cần thay thế vào vị trí của ```lower_bound()``` trong cú pháp trên - **Lưu ý⚠️:** Cẩn thận khi dùng lower_bound và upper_bound với $set, multiset$. Nếu bạn sử dụng `lower_bound(s.begin(), s.end(), x)` hoặc `upper_bound(s.begin(), s.end(), x)` thì độ phức tạp của nó thực chất là $O(n)$ chứ không phải là $O(\log{n})$ như bạn nghĩ. Vấn đề này có rất nhiều lập trình viên mắc phải và nó được nêu ra trong [[Tutorial] Common Mistakes in Competitive Programming and How to Avoid Them - Mistake 15](//codeforces.com/blog/entry/111217) **Code minh họa:** ```cpp=

include <bits/stdc++.h> using namespace std; int main() { set <int> s; // Thêm phân tử vào s s.insert(1); s.insert(3); s.insert(9); s.insert(18); s.insert(11); // Các phần tử của s khi này: s = { 1, 3, 9, 11, 18 } auto p1 = s.lower_bound(5); // Lưu trữ kết quả của hàm lower_bound vào p1 cout<< *p1 << "\n"; // Xuất giá trị của p1 auto p2 = s.upper_bound(13); // Lưu trữ kết quả của hàm upper_bound vào p2 cout<< *p2 << "\n"; // Xuất giá trị của p2 } ``` # Tìm kiếm nhị phân kết quả Ngoài những ứng dụng vô cùng hay ho và thú vị trên, binary search còn có một tính năng cực kì ưu việt là chúng ta có thể chặt nhị phân trên tập kết quả!!! Chúng ta hãy thử đưa bài toán về dạng tìm kiếm tuyến tính và cùng xem sự khác biệt giữa tìm kiếm tuyến tính và tìm kiếm nhị phân trên 1 tập kết quả là gì nhé. ## Bài toán ví dụ - Tất cả các số tự nhiên đều được chia ra là đẹp và xấu. Nếu $x$ là số đẹp thì $x + 1$ là số đẹp. Hãy tìm $x$ bé nhất là số đẹp. - Ta định nghĩa hàm kiểm tra $f(x)$ sẽ trả ra $1$ nếu $x$ là số đẹp ngược lại trả ra $0$ nếu $x$ là số xấu. - Để đơn giản, ta sẽ cho hàm $f(x)$ chỉ xác định khi $x$ nằm trong khoảng $l, r$. ### Tìm kiếm tuyến tính kết quả - Một cách đơn giản đó là chúng ta sẽ duyệt qua tập xác định $l, r$. Khi đó chúng ta chỉ cần tìm giá trị $x$ nhỏ nhất sao cho $f(x) = 1$. Nói đơn giản hơn là đề nói gì làm nấy. - Mã giả của thuật toán: ```cpp int linearSearch(int l, int r) { for (int i = l; i <= r; ++i) if (f(i) == 1) ans = min(ans, i) } ``` - Độ phức tạp thời gian: $O(r - l + 1)$ - Ta có thể thấy nếu khoảng cách giữa $l$ với $r$ (hay $r - l + 1$) $\le 10^5$ thì thuật toán này là hoàn toàn khả thi. Thế nhưng trong thực tế, tập xác định có thể lên đến $10^9, 10^{18},...$ thì thuật toán trên là bất khả thi. ### Tìm kiếm nhị phân kết quả - Để tối ưu thuật toán trên, chúng ta hãy xem xét tập kết quả có dạng như sau:  - Chúng ta có thể xem tập kết quả này là một dãy số, có thể thấy dãy số này được sắp xếp theo 1 trình tự nhất định **(thoả điều kiện để tìm kiếm nhị phân)**. Vậy chúng ta có thể tìm kiếm nhị phân như sau: - Đặt $left, right$ là vùng biên trái và vùng biên phải mà chúng ta cần xét. Vậy vùng biên trái của chúng ta cần xét ở đây là $l$ và vùng biên phải mà chúng ta cần xét ở đây là $r$. Hay $left = l, right = r$. - Tìm vị trí chính giữa của vùng biên: $m = \lfloor\frac{left + right}{2}\rfloor$ - Nếu $f(m) = 1$ ta sẽ cực tiểu hoá giá trị của $ans$ xuống bằng việc bỏ qua toàn bộ các giá trị trong đoạn từ $m \rightarrow right$. Lý do để bỏ qua là bởi vì ta biết rằng thông tin từ đoạn $m \rightarrow right$ thì hàm $f$ đều trả ra $1$ (đề cho). Thế nên chúng ta sẽ muốn biết xem liệu $m$ có phải là đáp án nhỏ nhất chưa. Hay đơn giản nếu $f(m) == 1$ thì chúng ta sẽ gán $right = m - 1$ và ghi nhận $m$ là kết quả hay $ans = m$. - Nếu $f(m) = 0$, chúng ta biết thông tin là đoạn từ $left \rightarrow m$ thì hàm $f$ đều trả ra $0$. Do đó, chúng ta sẽ bỏ qua đoạn $left \rightarrow m$ hay ta gán $left = m + 1$. - Kết quả nhỏ nhất cuối cùng của chúng ta sẽ được lưu trong biến $ans$. - Hãy cùng xem qua mã giả của thuật toán: ```cpp= bool f(int x) { // xử lí logic return true; // Thay giá trị này bằng giá trị đúng của logic } int binarySearch(int l, int r) { int left = l, right = r; // Đặt vùng biên trái và biên phải cần xét while (left <= right) { m = floor((left + right) / 2); // Tìm vị trí chính giữa với floor là hàm làm tròn xuống if (f(m) == 1) { // Nếu m hợp lệ. Bỏ qua các giá trị hợp lệ m -> right và ghi nhận m là kết quả right = m - 1; ans = m; } else left = m + 1; // Nếu m không hợp lệ. Bỏ qua tập left -> m không hợp lệ } return ans; // Kết quả cuối cùng } ``` - **Độ phức tạp thời gian:** Cũng giống như thuật toán tìm kiếm nhị phân bên trên, thế nhưng chúng ta sẽ nhân thêm độ phức tạp khi xử lí hàm $f(x)$ (ta gọi là $C$). Vậy tổng độ phức tạp của thuật toán trên là $O(C*\log(r - l + 1))$. - Minh hoạ quá trình tìm kiếm nhị phân kết quả:  ## Tổng quát ### Điều kiện để sử dụng tìm kiếm nhị phân - Là một hàm số đơn điệu. Hay nói đơn giản hơn hàm số đơn điệu là *một hàm đồng biến hoặc một hàm nghịch biến*. Trong ví dụ trên, hiển nhiên hàm $f$ là một hàm đồng biến. - **Định lí chính (Main Theorem)** cho biết rằng: một bài toán chỉ có thể áp dụng tìm kiếm nhị phân khi và chỉ khi hàm kiểm tra $f$ của bài toán thoả mãn các điều kiện sau: - Nếu $x$ hợp lệ thì với mọi $y \ge x$ thì $y$ hợp lệ. - Nếu $x$ không hợp lệ thì mọi $y \le x$ thì $y$ không hợp lệ. - Hoặc - Nếu $x$ hợp lệ thì với mọi $y \le x$ thì $y$ hợp lệ. - Nếu $x$ không hợp lệ thì mọi $y \ge x$ thì $y$ không hợp lệ. ### Cài đặt tổng quát - Trước khi cài đặt thuật toán, chúng ta phải trả lời những câu hỏi sau: - Liệu hàm kiểm tra $f(x)$ của ta có thoả mãn dạng $false - true$ ($false$ liên tiếp rồi đến $true$ liên tiếp) hay $true - false$ (ngược lại) không? - Bài toán có luôn có nghiệm hay không? Nếu không hãy kiểm tra trước để đỡ mất thời gian chạy nhé - Bạn đang muốn tìm giá trị lớn nhất hay giá trị nhỏ nhất - Hãy chắc chắn rằng nghiệm của bài toán nằm trong khoảng $l, r$ nhé!!! - Dưới đây sẽ là 2 mã giả cho 2 trường hợp lớn nhất và nhỏ nhất: - **TH1:** Tìm $x$ lớn nhất ```cpp bool f(int x) { // xử lí logic return true; // Thay giá trị này bằng giá trị đúng của logic } int binarySearch(int l, int r) { int left = l, right = r; // Đặt vùng biên trái và biên phải cần xét while (left <= right) { m = floor((left + right) / 2); // Tìm vị trí chính giữa với floor là hàm làm tròn xuống if (f(m) == 1) { // Nếu m hợp lệ. Bỏ qua các giá trị hợp lệ left -> m và ghi nhận m là kết quả left = m + 1; ans = m; } else right = m - 1; // Nếu m không hợp lệ. Bỏ qua tập m -> right không hợp lệ } return ans; // Kết quả cuối cùng } ``` - **TH2**: Tìm $x$ bé nhất ```cpp bool f(int x) { // xử lí logic return true; // Thay giá trị này bằng giá trị đúng của logic } int binarySearch(int l, int r) { int left = l, right = r; // Đặt vùng biên trái và biên phải cần xét while (left <= right) { m = floor((left + right) / 2); // Tìm vị trí chính giữa với floor là hàm làm tròn xuống if (f(m) == 1) { // Nếu m hợp lệ. Bỏ qua các giá trị hợp lệ m -> right và ghi nhận m là kết quả right = m - 1; ans = m; } else left = m + 1; // Nếu m không hợp lệ. Bỏ qua tập left -> m không hợp lệ } return ans; } ``` # Tìm kiếm nhị phân trên tập số thực - Ngoài tìm kiếm nhị phân trên tập số nguyên ra, chúng ta còn có thể tìm kiếm nhị phân trên tập số thực. Điểm khác biệt giữa tìm kiếm nhị phân trên tập số thực và số nguyên là không cần bận tâm về dịch chuyển cận và sai số. Chúng ta thường không tìm được giá trị mục tiêu một cách chính xác mà chỉ có thể xấp xỉ kết quả. Có 2 cách cài phổ biến mà mọi người thường dùng: - **Dừng sau một số lần nhất định (fixed):** Bình thường khi làm bài chúng ta chỉ cần lặp khoảng $100$ lần là đủ (có khi thừa) để đạt được độ chính xác mong muốn cho những dạng bài thế này. :::spoiler **Chứng minh sai số** - Nếu ta chọn: $m = \lfloor\frac{left + right}{2}\rfloor$ thì sau mỗi lần, độ lớn của đoạn $[left, right]$ sẽ giảm đi $\frac{1}{2}$ lần - Nếu ta lặp đi lặp lại $K$ lần, thì độ lớn của $[left, right]$ sẽ chỉ còn $(\frac{1}{2})K$ - Nếu $left = -10^9, right = 10^9$ ta lặp lại $K = 100$ lần thì $[left, right]$ thu về sẽ chỉ còn là $(\frac{1}{2}){100} * (2*10^9) < 10^{-20}$, đủ chính xác với hầu hết mọi bài toán. ::: - **Sai số tuyệt đối (absolute error):** Dừng khi $r - l \le ϵ$ ($ϵ$ thường rất nhỏ, khoảng $10^{-8}$). Cách này được sử dụng nếu thời gian chặt và bạn phải cố gắng tiết kiệm chi phí tính toán nhất có thể. - **Cách 1 (fixed):** ```cpp bool f(double x) { // xử lí logic return true; // Thay giá trị này bằng giá trị đúng của logic } double binarySearch(double l, double r) { double left = l, right = r; // Đặt vùng biên trái và biên phải cần xét for (int i = 1; i <= 100; ++i) { // Lặp 100 lần cho sai số là nhỏ nhất có thể double m = (left + right) / 2; // Tìm vị trí chính giữa if (f(m) == 1) { // Nếu m hợp lệ. Bỏ qua các giá trị hợp lệ m + 1 -> right và ghi nhận m là kết quả right = m; ans = m; } else left = m; // Nếu m không hợp lệ. Bỏ qua tập left -> m - 1 không hợp lệ } return ans; } ``` - **Cách 2 (absolute error):** ```cpp bool f(double x) { // xử lí logic return true; // Thay giá trị này bằng giá trị đúng của logic } double binarySearch(double l, double r) { double left = l, right = r; // Đặt vùng biên trái và biên phải cần xét while (right - left > 0.00000001) { // Nếu khoảng cách giữa right và left > ϵ rất bé thì mới lặp double m = (left + right) / 2; // Tìm vị trí chính giữa if (f(m) == 1) { // Nếu m hợp lệ. Bỏ qua các giá trị hợp lệ m + 1 -> right và ghi nhận m là kết quả right = m; ans = m; } else left = m; // Nếu m không hợp lệ. Bỏ qua tập left -> m - 1 không hợp lệ } return ans; } ``` # Bài tập vận dụng ## Bài 1: [CSES - Concert Tickets](//cses.fi/problemset/task/1091/) #### Tóm tắt - Có $n$ vé đi xem concert ca nhạc có sẵn, mỗi vé có $1$ giá bán nhất định. Sau đó có $m$ người khách hàng đến mua vé, lần lượt từng người một. Mỗi người ra giá cao nhất mà họ có thể mua, sau đó họ sẽ nhận được một vé có giá lớn nhất sao cho không vượt quá giá tối đa. - Dòng đầu gồm $2$ số $n, m$ lần lượt là số lượng vé và số lượng khách hàng. - Dòng thứ $2$ gồm $h_1, h_2, ..., h_n$ là giá của vé thứ $i$. - Dòng thứ $3$ gồm $t_1, t_2, ..., t_m$ là giá tối đa mà khách hàng thứ $i$ có thể trả. - In ra giá mà người thứ $i$ sẽ mua, nếu không có vé thì in ra $-1$. - $1 \le n,m \le 2⋅10^5, 1 \le h_i,t_i \le 10^9$ #### Input ``` 5 3 5 3 7 8 5 4 8 3 ``` #### Output ``` 3 8 -1 ``` ## Bài 2: [CSES - Factory Machines](//cses.fi/problemset/task/1620/) #### Tóm tắt - Một nhà máy có $n$ máy móc có thể được sử dụng để sản xuất sản phẩm. Mục tiêu là sản xuất ra $t$ sản phẩm, biết máy thứ $i$ sản xuất một sản phẩm trong $k_i$ đơn vị thời gian, các máy có thể sử dụng song song nhau. Hỏi thời gian tối thiểu để sản xuất $t$ sản phẩm là bao nhiêu? - $1 \le n \le 2*10^5, 1 \le t, k_i \le 10^9$ #### Input ``` 3 7 3 2 5 ``` #### Output ``` 8 ``` #### Giải thích - Máy $1$ sản xuất $2$ sản phẩm, máy $2$ sản xuất $4$ sản phẩm, máy $3$ sản xuất $1$ sản phẩm. Thời gian tối thiểu để sản xuất $7$ sản phẩm là $max(3*2, 2*4, 5*1) = 8$ ## Bài 3: [CSES - Array Division](//cses.fi/problemset/task/1085) #### Tóm tắt - Cho một mảng $a$ gồm $n$ số nguyên dương. Tìm cách chia $k$ mảng con liên tiếp sao cho tổng lớn nhất của các mảng con là nhỏ nhất. - $1 \le k \le n \le 2*10^5, 1 \le x_i \le 10^9$ #### Input ``` 5 3 2 4 7 3 5 ``` #### Output ``` 8 ``` #### Giải thích Một cách chia tối ưu như sau: $[2, 4], [7], [3, 5]$ và tổng của mỗi mảng con là $6, 7, 8$. Tổng lớn nhất là $8$. ## Bài 4: [TS10 TPHCM - Đào Vàng](//gdoj.eu.org/problem/chope_daovang) #### Tóm tắt - Có $N$ thỏi vàng được đặt ở các vị trí $x_1, x_2, ... x_N$ trên trục nằm ngang. Nếu đặt máy khoan có lực đập $R$ tại vị trí $X$ thì có thể lấy được các thỏi vàng nằm trong khoảng từ $[X - R, X + R]$. Người chơi có tối đa $K$ lần đặt máy. Hãy giúp người chơi chọn lực đập $R$ nhỏ nhất để có thể đào hết $N$ thỏi vàng. - $K \le 20, N \le 50000, x_i \le 10^9$ #### Subtask - $20\%$ test ứng với $20\%$ số điểm của bài có $K = 1$ và $N \le 1000$ - $20\%$ test ứng với $20\%$ số điểm của bài có $K = 2$ và $N \le 10000$ - $60\%$ test ứng với $60\%$ số điểm của bài có $K \le 20$ và $N \le 50000$ #### Input 1 ``` 6 1 2 20 6 5 4 17 ``` #### Output 1 ``` 9 ``` #### Giải thích Với lực đập $R = 9$, người chơi có thể đặt máy khoan $1$ lần tại điểm $X_1 = 11$. #### Input 2 ``` 6 2 2 20 6 5 4 17 ``` #### Output 2 ``` 2 ``` #### Giải thích Với lực đập $R = 2$, người chơi có thể đặt máy khoan $2$ lần tại $X_1 = 4, X_2 = 18$ # Luyện tập thêm - [VNOJ - NKSGAME](//oj.vnoi.info/problem/nksgame) - [VNOJ - POWER](//oj.vnoi.info/problem/power) - [CF - Sushi for Two](//codeforces.com/problemset/problem/1138/A) - [CF - Cellular Network](//codeforces.com/contest/702/problem/C) - [CF - Guess the K-th Zero](//codeforces.com/contest/1520/problem/F1) - [TS10 QNi - Mật mã kho báu](//tleoj.edu.vn/problem/edu016d) # Tham khảo :::info - [[1] VNOI - Thuật toán tìm kiếm nhị phân](//vnoi.info/wiki/algo/basic/binary-search.md) - [[2] CP Handbook](//cses.fi/book/book.pdf) - [[3] CF Edu - Binary Search](//codeforces.com/edu/course/2/lesson/6) - [[4] USACO GUIDE](//usaco.guide/silver/binary-search?lang=cpp) - [[5] VIBLO](//viblo.asia/p/tim-kiem-nhi-phan-tren-tap-ket-qua-ByEZkeAY5Q0) - [[6] Blog Gã coder si tình - Bàn về cài đặt Binary Search](//hackmd.io/@callmelucian/S1akCO07n) - [[7] 2SG Tin học - Tìm kiếm trong mảng](//drive.google.com/file/d/1GHuevPLD_IbBpZRIEXpLU6XJXIwKDpaP/view?usp=/share_link) - [[8] GeeksforGeeks](//www.geeksforgeeks.org/) :::