Tài liệu ứng dụng phương pháp tìm kiếm trong việc giải các bài toán thi học sinh giỏi môn tin

ỨNG DỤNG PHƯƠNG PHÁP TÌM KIẾM TRONG VIỆC GIẢI CÁC BÀI TOÁN THI HỌC SINH GIỎI MÔN TIN HỌC MÃ: TI17 1. CƠ SỞ LÝ THUYẾT 1.1. Phát biểu bài toán Cho một dãy gồm n bản ghi r[1..n]. Mỗi bản ghi r[i] (1 ≤ i ≤ n) tương ứng với một khóa k[i]. Hãy tìm một bản ghi có giá trị khóa bằng X cho trước. X được gọi là khóa tìm kiếm. Công việc tìm kiếm sẽ hoàn thành nếu như một trong hai tình huống sau sảy ra: • Tìm được bản ghi có khóa tương ứng bằng X, lúc đó phép tìm kiếm thành công. • Không tìm được bản ghi nào có khóa tương ứng bằng X, lúc đó phép tìm kiếm thất bại. 1.2. Phương pháp tìm kiếm tuần tự 1.2.1. Nội dung thuật toán Bắt đầu từ bản ghi đầu tiên, lần lượt so sánh khóa tìm kiếm với khóa tương ứng của các bản ghi trong danh sách, cho tới khi tìm thấy bản ghi mong muốn hoặc duyệt hết danh sách mà không thấy. 1.2.2. Nội dung chương trình * Code của ngôn ngữ lập trình PASCAL Function  TK_tuantu(X:  Key):  integer;   var  i:  Integer;   Begin     for  i:=1  to  n  do       if  (r[i]  =  X)  then  exit(i);{tìm  thấy  X  thì  trả  ra  vị  trí  của  nó}     exit(0);  {không  tìm  thấy  X  thì  trả  ra  vị  trí  0}   End; * Code của ngôn ngữ lập trình C++ 1 int  TK_tuantu(int  X)   {     for  (int  i  =  1;  i  <=  n;  i++)     if  (r[i]  ==  X)  return  i;{tìm  thấy  X  thì  trả  ra  vị  trí  của  nó}     return  0;   } 1.2.3. Đánh giá độ phức tạp của thuật toán: Thuật toán có độ phức tạp tốt nhất là O(1), khi K[1] = X và xấu nhất là O(N) khi không tìm được X trong danh sách khóa. Như vậy độ phức tạp của thuật toán là O(N). 1.3 Phương pháp tìm kiếm nhị phân Phương pháp tìm kiếm nhị phân được áp dụng trên dãy khóa đã sắp thứ tự. Tức là K[1] ≤ K[2] ≤ ... ≤ K[n] 1.3.1. Nội dung thuật toán Giả sử cần tìm X trong đoạn K[L ... R] (L ≤ R), trước hết ta xét khóa nằm giữa đoạn K[Mid] với Mid = (L + R) div 2; • Nếu K[Mid] < X nghĩa là đoạn K[L ... Mid] chứa toàn khóa < X. khi đó ta tiến hành tìm kiếm X trên đoạn K[Mid+1 ... R] • Nếu K[Mid] > X nghĩa là đoạn K[L ... Mid] chứa toàn khóa > X. khi đó ta tiến hành tìm kiếm X trên đoạn K[R ... Mid - 1] • Nếu K[Mid] = X thì tìm kiếm thành công (kết thúc quá trình tìm kiếm). Quá trình tìm kiếm sẽ thất bại nếu một bước nào đó đoạn tìm kiếm là rỗng tức là L>R 1.3.2. Nội dung chương trình * Code của ngôn ngữ lập trình PASCAL Function  TK_NhiPhan(X:  Key):  integer;   var  L,R,Mid:integer;   Begin     L  :=  1;  R  :=  N;     While  (L  <=  R)  do   2   Begin       Mid  :=  (L  +  R)  div  2;       if  K[Mid]  =  X  then  exit(Mid);  {tìm  thấy  x  thì  trả  ra  kết  quả  tìm   được  là  vị  trí  của  nó}       if  K[Mid]    <  X  then  L  :=  Mid  +  1       else   R  :=  Mid  –  1;     end;     exit(0);  {không  tìm  thấy  x  thì  trả  ra  kết  quả  bằng  0}   End;   * Code của ngôn ngữ lập trình C++ int  TK_NhiPhan(int  X)   {     int  L,  R,  Mid;     while  (L  <=  R)     {       Mid  =  (L+R)/2;       if  (K[Mid]  ==  X)  return  Mid;  {tìm  thấy  x  thì  trả  ra  kết  quả  tìm   được  là  vị  trí  của  nó}       if  (K[Mid]  <  X)  L  =  Mid  +  1;       else  R  =  Mid  –  1;     }     return  0;  {không  tìm  thấy  x  thì  trả  ra  kết  quả  bằng  0}   }   1.3.3. Độ phức tạp thuật toán. Người ta chứng minh được độ phức tạp tính toán của thuật toán tìm kiếm nhị phân trong trường hợp tốt nhất là O(1), trong trường hợp xấu nhất là O(lgN). Tuy nhiên không nên quên rằng trước khi sử dụng phương pháp tìm kiếm nhị phân thì dãy khóa phải được sắp xếp, tức là thời gian chi phí cho việc sắp xếp phải được tính đến. 1.3.4. Mở rộng phương pháp tìm kiếm nhị phân Trong các bài toán Tin học, có những bài toán không chỉ đơn thuần tìm vị trí của khóa X trong một dãy đối tượng được sắp xếp mà có thể là tìm phần tử có khóa nhỏ nhất lớn hơn X (hoặc tìm phần tử có khóa lớn nhất nhỏ hơn X). Khi đó vẫn sử dụng tìm kiếm nhị phân nhưng cần cải tiến một chút trong hàm tìm kiếm này. Ví dụ: dùng tìm kiếm nhị phân để tìm phần tử có giá trị nhỏ nhất lớn hơn X trong dãy phần tử đã sắp xếp tăng dần. 3 * Code của ngôn ngữ lập trình PASCAL function  tk_NhiPhan(x:  integer):  integer;   var     L,  R,  Mid:  integer;   Begin     L  :=  1;  R  :=  N;     while  (L  <=  R)  do     Begin       Mid  :=  (L  +  R)  div  2;       if  (K[Mid]  <=  X)  then  L  :=  Mid  +  1       else  R  :=  Mid  –  1;   end;     exit(L);   End;   * Code của ngôn ngữ lập trình C++: int  TK_NhiPhan(int  X)   {     int  L,  R,  Mid;     while  (L  <=  R)     {       Mid  =  (L+R)/2;       if  (K[Mid]  <=  X)  L  =  Mid  +  1;       else  R  =  Mid  –  1;     }     return  L;     }   Tương tự, ta có thể tìm phần tử lớn nhất nhỏ hơn giá trị X. 2. BÀI TẬP ÁP DỤNG Bài 1. Dãy con Cho một dãy số nguyên dương a1, a2, ..., aN (10 < N < 100.000), ai ≤ 10.000 với mọi i=1..N và một số nguyên dương S (S < 100.000.000). Yêu cầu : Tìm độ dài nhỏ nhất của dãy con chứa các phần tử liên tiếp của dãy mà có tổng các phần tử lớn hơn hoặc bằng S. Dữ liệu vào: Đọc từ file SUB.INP gồm 2 dòng, dòng 1 chứa N và S ở dòng đầu. Dòng 2 chứa các phần tử của dãy. Dữ liệu ra: Kết quả ghi vào file SUB.OUT, chứa độ dài của dãy con tìm được. 4 Ví dụ : SUB.INP SUB.OUT 10 15 2 5 1 3 5 10 7 4 9 2 8 * Hướng dẫn giải: Bài toán này có thể giải theo 2 cách sau: Cách 1: dễ dàng giải bài toán với 1 cách làm trâu bò là xét 2 vòng lặp lồng nhau để tìm tất cả các tổng của các đoạn con đồng thời kết hợp tìm đoạn con có tổng >= S và có số phần tử ít nhất. Độ phức tạp là O(N2) Cách 2: Sử dụng phương pháp tìm kiếm nhị phân để giải bài toán: Gọi T[i] là tổng của các số A[1] đến A[i]. Vì A[i] là các số dương => Dãy T là dãy tăng dần. Khi đó ta sẽ tiến hành tìm kiếm nhị phân trên dãy T như sau: * Xét T[i]: d = 1, c = i-1, g = (d + c) div 2 Nếu T[i] – T[g] >= S thì kq = min(kq, i – g) và tìm kq tiếp tục ở đoạn bên phải T[g] Nếu T[i] – T[g] < S thì tìm kq ở đoạn bên trái T[g]. Độ phức tạp là O(NlogN). Có cách thứ 3 với độ phức tạp là O(N), xin phép không đề cập ở đây vì cách này không sử dụng phương pháp tìm kiếm nhị phân. 5 Bài 2: Đếm tam giác Cho 3 dãy số dương A, B, C cùng có N phần tử. Hãy đếm xem có bao nhiêu bộ 3 số A[i], B[j] và C[k] mà 3 số này là 3 cạnh của 1 tam giác. Dữ liệu vào: từ file TRIANGLE.INP với cấu trúc: - Dòng đầu chứa số nguyên n (n <= 1000) - Dòng thứ hai chứa các số A1, A2, ..., An. - Dòng thứ ba chứa các số B1, B2, ..., Bn. - Dòng thứ tư chứa các số C1, C2, ..., Cn. Các số ai, bi, ci đều không vượt quá 104 và được ghi cách nhau bởi dấu cách. Dữ liệu ra: file văn bản TRIANGLE.OUT gồm một số S duy nhất là số lượng bộ ba số tìm được. TRIANGLE.INP TRIANGLE.OUT TRIANGLE.INP TRIANGLE.OUT 2 3 2 23 231 31 449 47 852 8 * Hướng dẫn: Chúng ta có thể giải bài này bằng 2 cách như sau: Cách 1: Bài toán được giải một cách dễ dàng bằng phương pháp vét cạn: dùng 3 vòng lặp lồng nhau để xét từng bộ ba số (ai, bj, ck). Độ phức tạp là O(N3). Cách 2 Ta có cách giải với độ phức tạp là O(N2*logN) như sau: 6 - Trước hết ta giải bài toán phụ như sau: Cho dãy không giảm A, và hai số x < y. Hãy sử dụng phương pháp tìm kiếm nhị phân để đếm xem có bao nhiêu số A[i] thỏa mã x < A[i] < y. Giải: Bước 1: Viết hàm TimKiem1(x): để tìm vị trí i1 nhỏ nhất mà tại đó A[i1] > x, sử dụng phần mở rộng của tìm kiếm nhị phân. Bước 2: Viết hàm TimKiem2(y): để tìm vị trí i2 lớn nhất mà tại đó A[i2] < y, sử dụng phần mở rộng của tìm kiếm nhị phân. Kq = i2 – i1 + 1 Dựa vào bài toán phụ ở trên ta giải bài toán TRIANGLE như sau: Ta có nhận xét: Ba số a[i], b[j], c[k] là 3 cạnh của một tam giác khi và chỉ khi thỏa mãn hệ thức: |a[i] – b[j]| c1 thì § Tìm kiếm số |ai – bj| trong dãy c bằng phương pháp tìm kiếm nhị phân được vị trí l § Tìm kiếm số ai+bj trong dãy c bằng phương pháp tìm kiếm nhị phân được vị trí k § Nếu k >= l thi dem = dem + k – l + 1; 7 Bài 3. Trò chơi với dãy số Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây. Mỗi bạn chọn trước một dãy số gồm n số nguyên. Giả sử dãy số mà bạn thứ nhất chọn là: b1, b2, ..., bn còn dãy số mà bạn thứ hai chọn là c1, c2, ..., cn Mỗi lượt chơi mỗi bạn đưa ra một số hạng trong dãy số của mình. Nếu bạn thứ nhất đưa ra số hạng bi (1 <= i <= n), còn bạn thứ hai đưa ra số hạng cj (1 <= j <= n) thì giá của lượt chơi đó sẽ là |bi+cj|. Ví dụ: Giả sử dãy số bạn thứ nhất chọn là 1, -2; còn dãy số mà bạn thứ hai chọn là 2, 3. Khi đó các khả năng có thể của một lượt chơi là (1, 2), (1, 3), (-2, 2), (-2, 3). Như vậy, giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể là 0 tương ứng với giá của lượt chơi (-2, 2). Yêu cầu: Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể. INPUT: vào từ file văn bản SEQGAME.INP - Dòng đầu là số nguyên dương (1 <= n <= 105) - Dòng thứ hai chứa các số là dãy b (|bi| <= 109) - Dòng thứ hai chứa các số là dãy c (|ci| <= 109) OUTPUT: ghi ra file văn bản SEQGAME.OUT giá trị nhỏ nhất tìm được Ví dụ: Ràng buộc: 60% số test ứng với 60% số điểm có 1<= n <= 1000 Hướng dẫn giải Bài toán có thể giải bằng 2 cách: Cách 1: Sử dụng 2 vòng lặp lồng nhau để tìm giá trị nhỏ nhất. Độ phức tạp là O(N2) 8 Cách 2: Sử dụng phương pháp tìm kiếm nhị phân như sau: Bước 1: Sắp xếp dãy A tăng dần Bước 2: xét các giá trị B[i]. Xét các giá trị A[g] (g = (d + c) div 2 với d = 1, c = N) Min := A[g] + B[i] - Nếu A[g] + B[i] < 0 thì phải tăng g lên để tổng gần 0 hơn khi đó d := g + 1 - Nếu A[g] + B[j] > 0 thì phải giảm g xuống để tổng gần 0 hơn khi đó c := g – 1. - Nếu Min = 0 thì thoát Kq = |Min| Độ phức tạp là O(NlogN). Bài 4. Đóng gói sản phẩm. (nguồn bài: Đề thi HSG QG bảng B – năm 2005). Ở đầu ra của một dây chuyền sản xuất trong nhà máy ZXY có một máy xếp tự động. Sau khi kết thúc việc gia công trên dây chuyền, các sản phẩm sẽ được xếp vào các hộp có cùng dung lượng M. Sản phẩm rời khỏi dây chuyền được xếp vào hộp đang mở (khi bắt đầu ca làm việc có một hộp rỗng được mở sẵn) nếu như dung lượng của hộp còn đủ để chứa sản phẩm. Trong trường hợp ngược lại, máy sẽ tự động đóng nắp hộp hiện tại, cho xuất xưởng rồi mở một hộp rỗng mới để xếp sản phẩm vào. Trong một ca làm việc có n sản phẩm đánh số từ 1 đến n theo đúng thứ tự mà chúng rời khỏi dây chuyền. Sản phẩm thứ i có trọng lượng là ai, i = 1, 2, …, n. Ban Giám đốc nhà máy qui định rằng sản phẩm xuất xưởng của mỗi ca làm việc phải được xếp vào trong không quá k hộp. Yêu cầu: Hãy giúp người quản đốc của ca làm việc xác định giá trị M nhỏ nhất sao cho số hộp mà máy tự động cần sử dụng để xếp dãy n sản phẩm xuất xưởng của ca không vượt quá số k cho trước. Dữ liệu: Vào từ file văn bản ZXY.INP: • Dòng đầu tiên chứa hai số nguyên n và k, (1 <= k <= n <= 15000); 9 • Dòng thứ i trong n dòng tiếp theo chứa số nguyên dương ai (ai <= 30000), i =1, 2, …, n. Các số trên một dòng cách nhau ít nhất một dấu cách. Kết quả: Ghi ra file ZXY.OUT một số nguyên duy nhất là dung lượng của hộp. Ví dụ: *Hướng dẫn: Bài toán này hoàn toàn có thể giải quyết được bằng phương pháp tìm kiếm nhị phân. Gọi Max là trọng lượng lớn nhất trong n hộp, S là tổng trọng lượng n hộp. Chúng ta sẽ chặt nhị phân trong đoạn từ Max -> S để tìm M (vì M chắc chắn nằm trong đoạn từ Max -> S) như sau: d := Max; c := S; Lặp khi d <= c: - M := (d + c)/2 - Dem = so lượng hộp trọng lượng M có thể chứa được n vật phẩm - Nếu dem > k nghĩa là M quá nhỏ vì vậy cần tăng kích thước của M bằng cách chặt nhị phân tìm M trong đoạn từ d = M + 1 -> c - Ngược lại: M đã thỏa mãn có thể chứa được n vật phẩn, tuy nhiên M có thể chưa là giá trị nhỏ nhất. Vì vây lưu lại giá trị kq = M, và tìm M có giá trị nhỏ hơn bằng cách chặt nhị phân tìm M trong đoạn từ d -> c = M - 1 Bài 5: Robot cứu hỏa. (Nguồn bài: Đề thi HSG QG 2007). Trên một mạng lưới giao thông có n nút, các nút được đánh số từ 1 đến n và giữa hai nút bất kỳ có không quá một đường nối trực tiếp (đường nối trực tiếp là một đường hai 10 chiều). Ta gọi đường đi từ nút s đến nút t là một dãy các nút và các đường nối trực tiếp có dạng: s = u1, e1, u2,..., ui, ei, ui+1, ..., uk-1, ek-1, uk = t, trong đó u1, u2, …, uk là các nút trong mạng lưới giao thông, ei là đường nối trực tiếp giữa nút ui và ui+1 (không có nút uj nào xuất hiện nhiều hơn một lần trong dãy trên, j = 1, 2, …, k). Biết rằng mạng lưới giao thông được xét luôn có ít nhất một đường đi từ nút 1 đến nút n. Một robot chứa đầy bình với w đơn vị năng lượng, cần đi từ trạm cứu hoả đặt tại nút 1 đến nơi xảy ra hoả hoạn ở nút n, trong thời gian ít nhất có thể. Thời gian và chi phí năng lượng để robot đi trên đường nối trực tiếp từ nút i đến nút j tương ứng là tij và cij (1 <= i, j <= n). Robot chỉ có thể đi được trên đường nối trực tiếp từ nút i đến nút j nếu năng lượng còn lại trong bình chứa không ít hơn cij (1 <= i, j <= n). Nếu robot đi đến một nút có trạm tiếp năng lượng (một nút có thể có hoặc không có trạm tiếp năng lượng) thì nó tự động được nạp đầy năng lượng vào bình chứa với thời gian nạp coi như không đáng kể. Yêu cầu: Hãy xác định giá trị w nhỏ nhất để robot đi được trên một đường đi từ nút 1 đến nút n trong thời gian ít nhất. Input: Đọc từ file QBROBOT.INP: · Dòng đầu tiên chứa một số nguyên dương n (2 <= n <= 500); · Dòng thứ hai chứa n số, trong đó số thứ j bằng 1 hoặc 0 tương ứng ở nút j có hoặc không có trạm tiếp năng lượng (j = 1, 2, …, n); · Dòng thứ ba chứa số nguyên dương m (m <= 30000) là số đường nối trực tiếp có trong mạng lưới giao thông; · Dòng thứ k trong số m dòng tiếp theo chứa 4 số nguyên dương i, j, tij, cij (tij, cij <= 10000) mô tả đường nối trực tiếp từ nút i đến nút j, thời gian và chi phí năng lượng tương ứng. Hai số liên tiếp trên một dòng trong file dữ liệu cách nhau ít nhất một dấu cách. 11 Output: Ghi ra file QBROBOT.OUT: Ghi ra số nguyên dương w tìm được. Ví dụ: QBROBOT.INP 4 QBROBOT.OUT 3 0110 5 1254 1343 1494 2441 3452 * Hướng dẫn giải: Trước hết ta nhận thấy rằng thời gian đi nhỏ nhất từ 1 -> N được ưu tiên hàng đầu. Vì vậy dùng Dijkstra để tìm đường đi ngắn nhất từ 1 -> N, gọi d[i] là khoảng cách nhỏ nhất từ i -> N. Sau đó sẽ tìm giá trị w nhỏ nhất mà có thể đi với thời gian ngắn nhất vừa tìm được là d[1]. Bài toán có thể giải quyết bằng phương pháp tìm kiếm nhị phân như sau: Vì w chắc chắn nằm trong đoạn từ 1 -> + ∞ nên: d := 1 và c := 100000000; Lặp khi d <= c - w := (d + c)/2 - Thực hiện tìm kiếm theo chiều sâu bắt đầu từ đỉnh 1 tìm đến đỉnh N: o Nếu không tìm được đường đi từ 1 -> N với thời gian ngắn nhất (nghĩa là w hơi bé) cần tăng giá trị w lên bằng cách chặt nhị phân tìm w từ d := w + 1 >c 12 o Ngược lại: w đã thoản mãn có thể đi từ 1 -> N với thời gian ngắn nhất. Tuy nhiên w chưa chắc là nhỏ nhất. Vì vậy cần giảm giá trị w bằng cách chặt nhị phân trong đoạn từ d -> c = w – 1 - Vấn đề cần giải quyết bây giờ là trong thủ tục DFS(1) thì điều kiện để đi từ đỉnh u -> v là gì? - Câu hỏi trên sẽ được giải đáp nếu trả lời được 3 câu hỏi sau: o Từ u -> v có đường đi trực tiếp không? nếu có đường đi trực tiếp thì trả lời câu hỏi tiếp. o Đỉnh u có trạm tiếp năng lượng không? hoặc năng lượng còn lại của robot có thể đi từ u -> v không. Nếu thỏa mãn thì trả lời câu hỏi tiếp: o Đường đi từ u -> v có đảm bảo là nằm trên một đường đi từ 1 -> N với thời gian ngắn nhất không? tức là tổng thời gian từ 1 –> u với t(u,v) và d[v] có bằng d[1] không? Bài 6. Chiều cao xe Đất nước Alpha có N thành phố và M cây cầu hai chiều nối trực tiếp một số thành phố, các cặp thành phố hoặc có đường đi trực tiếp, hoặc có đường đi qua các đỉnh trung gian. Tại mỗi cây cầu có ghi giới hạn độ cao tối đa của xe khi chạy qua nó. Thủ đô của đất nước Alpha được đặt tại thành phố s, đất nước có một thành phố t là khu khai thác tài nguyên khoáng sản vô cùng lớn. Tài nguyên khoáng sản sau khi được khai thác sẽ chuyển lên các xe ô tô tải và chở về thủ đô. Để có thể khai thác triệt để nguồn tài nguyên, người ta phải dùng các xe ô tô có công ten nơ (biết các xe đủ khỏe để có thể chịu được trọng tải của công ten nơ), tuy nhiên khi qua các cầu thì lại bị giới hạn về chiều cao, vì vậy cần thiết kế sao cho chiều cao của xe khi chở các công ten nơ là cao nhất để các xe có thể chở nguồn tài nguyên về thủ đô. Yêu cầu: Hãy tìm chiều cao lớn nhất của xe khi chở các công ten nơ. Input: Đọc từ file height.inp: - Dòng đầu tiên là hai số N, M, s, t. (2 <= N <= 104, 1 <= M <= 105) 13 - M dòng tiếp theo, mỗi dòng là 3 số u, v, c cho biết cầu nối thành phố u tới thành phố v có chiều cao giới hạn là c (1 <= c <= 104). Output: ghi ra file height.out: - Dòng đầu tiên là chiều cao lớn nhất tìm được. - Dòng thứ 2 đường đi ngắn nhất từ đỉnh s đến t với chiều cao vừa tìm được. Ví dụ height.inp height.ou 6 9 1 5 4 Hình vẽ 1 2 3 4 5 1 2 4 1 6 1 3 2 4 4 2 3 6 2 4 3 5 4 1 2 6 4 6 7 5 3 1 3 4 7 6 3 5 3 5 3 3 6 5 4 5 5 * Hướng dẫn giải: Ta sẽ tìm kiếm kết quả thuộc đoạn 1 -> Max{cạnh đồ thị} bằng phương pháp tìm kiếm nhị phân: L = 1; R = max; - Lặp khi L <= R; + Mid = (L+R) /2; + Nếu check(Mid) thì { kq = Mid; 14 R = Mid – 1; } ngược lại thì L = Mid + 1; Trong đó hàm check(Mid) dùng để kiểm tra xem liệu với chiều cao Mid thì xe có thể đi từ s đến t không? (có thể dùng thuật toán DFS(s) hoặc BFS(s) để kiểm tra điều này). Nếu check(Mid) = true thì hi vọng tìm được giá trị Mid nhỏ hơn nữa bằng cách giảm giá trị R = Mid – 1. Nếu check(Mid) = false thì giá trị Mid là quá nhỏ nên phải tăng giá trị này lên bằng cách thay đổi giá trị L = Mid + 1. 3. Kết luận Nhìn chung các bài toán được ứng dụng phương pháp tìm kiếm nhị phân thường đi cặp với thuật toán sắp xếp, và hầu như các bài toán đều là những bài toán ở mức độ không khó về mặt giải thuật. Tuy nhiên nó lại được đưa vào nhiều đề thi HSG các cấp, và nếu như học sinh được làm quen nhiều với các dạng bài toán này thì việc nhận dạng và giải chúng là điều mà các em có thể làm được rất tốt. Trong bài viết của tôi có lẽ còn sơ sài, nhiều thiếu sót, rất mong được sự đóng góp của các đồng nghiệp để chuyên đề được hay hơn và hoàn thiện hơn. Xin trân trọng cảm ơn! 15