Bước 1: Cắt mảng làm 2 phần bằng nhau
- VD: dãy A = [1, 2, 3, 4] thì được cắt thành [1, 2] và [3, 4]
Bước 2: XÉT từng phần của mảng:
- Nếu phần ĐANG ĐƯỢC XÉT chỉ có 1 phần tử: Xử lý bài toán
- Ngược lại:
Bước 3: Cắt phần đó làm đôi
Bước 4: quay về bước 2
Chặt nhị phân là 1 phép chia để trị.
Code chặt nhị phân (trong Pascal) sẽ là như sau:
procedure BinarySearch(startnum, endnum: longint);
var midnum: longint;
begin
if (startnum = endnum) then
xử_lý_bài_toán
else begin
midnum := (startnum + endnum) div 2;
BinarySearch(startnum, midnum);
BinarySearch(midnum + 1, endnum);
end;
end;
Trong đó startnum là số đầu, endnum là số cuối, midnum là trung bình cộng của 2 số.
Cộng thêm điều kiện của đề bài, code sẽ như sau (mình chỉ làm sample thôi nha):
procedure BinarySearch(startnum, endnum: longint);
var midnum, x: longint;
begin
if (startnum = endnum) then
begin //Xử lý bài toán
x := abs(Sum(L, startnum) – Sum(startnum + 1, R));
if (x < min) then
min := x;
end
else begin //Tiếp tục chặt nhị phân, tách phần được xét làm đôi
midnum := (startnum + endnum) div 2;
BinarySearch(startnum, midnum);
BinarySearch(midnum + 1, endnum);
end;
end;
begin
…
Start(L, R);
…
end.
Trong đó: Sum(x, y) là tổng các số nguyên từ x đến y.