Tuesday, March 14, 2017
CHƯƠNG III, TÌM KIẾM NHỊ PHÂN (CHẶT NHỊ PHÂN).
1. Thuật toán
Phát
biểu bài toán: Cho dãy số a1, a2, …an đã được sắp xếp không giảm.
Yêu cầu: Tìm xem giá trị X có nằm trong dãy số hay không
Nếu ta dùng thuật toán tìm kiếm tuần tự
thì độ phức tạp của bài toán là O(n). Vì bài toán đã cho dãy đã được sắp xếp
tăng nên chúng ta dùng tìm kiếm nhị phân để giảm độ phức tạp của bài toán xuống
còn O(logN).
////////Đoạn codeo tham khảo
dau:= 1; cuoi:= n;
while dau
<= cuoi do
begin
giua:= (dau+cuoi) div 2;
if x = a[giua] then
begin
writeln(x,’ co trong day’);
break;
end;
else if x < a[giua] then
cuoi:= giua -1
else dau:= giua+1;
end;
