Bài toán
Cho một mảng không giảm, tìm phần tử đầu tiên mà lớn hơn hoặc bằng một số cho trước.
Độ phức tạp
O(logn)
Code này của : Nguyễn Tiến Trung Kiên
{$mode objfpc}
{$coperators on}
function bsearch(const a : array of integer; n, key : integer) : integer;
var ll, rr, i : integer;
begin
ll := 1; rr := n; i := (ll+rr) div 2;
while (ll<>i) and (rr<>i) do
begin
if a[i]>=key
then rr := i
else ll := i;
i := (ll+rr) div 2;
end;
for i := ll to rr do
if a[i]>=key then exit(i);
exit(0);
end;
var a : array [0..1230997] of integer;
n, key : integer;
var i : integer;
begin
readln(n);
for i := 1 to n do
read(a[i]);
while not seekeof do
begin
readln(key);
i := bsearch(a, n, key);
if i=0 then writeln('Not found')
else writeln(a[i]);
end;
end.
Nhận xét