- 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 xuat ra "YES" va thoat ra khoi ham if[a[i] == x]{ cout xuat ra "NO" cout 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$. ![][//hackmd.io/_uploads/S1K4YNcn3.png] - 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$. ![][//hackmd.io/_uploads/r1j5tE9nh.png] - 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: ![][//hackmd.io/_uploads/HJNVNOi2h.png] Minh hoạ quá trình tìm kiếm phần tử $x$: ![][//hackmd.io/_uploads/HJGS14cn3.gif] 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 x] right = mid - 1; //Phan tu o vi tri mid < x else left = mid + 1; } //Khong tim thay phan tu thoa de cout 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 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. ![][//hackmd.io/_uploads/ByjgyDcnh.png] - 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: ![][//hackmd.io/_uploads/Sk7TfVoh3.png] 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 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 x; //Khai bao pair gom 2 con tro auto r = equal_range[a.begin[], a.end[], 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 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 r } // Trả về vị trí lớn nhất có giá trị = x thì ta bỏ qua đoạn mid -> r và ghi nhận mid là 1 kết quả hợp lệ } else { l = 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: ![][//hackmd.io/_uploads/HJuDhS5h2.gif] ## 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=