binarysearch.pas

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