62 lines
1.4 KiB
ObjectPascal
62 lines
1.4 KiB
ObjectPascal
function BinarySearch(a: array of integer; x: integer): integer;
|
|
begin
|
|
var (l,r) := (0, a.Length-1);
|
|
repeat
|
|
var mid := (l + r) div 2;
|
|
if x = a[mid] then
|
|
begin
|
|
Result := mid;
|
|
exit
|
|
end;
|
|
if x > a[mid] then
|
|
l := mid + 1
|
|
else r := mid - 1;
|
|
until l > r;
|
|
Result := -1;
|
|
end;
|
|
|
|
function BinarySearchRecursive(a: array of integer; x: integer): integer;
|
|
function BinarySearchHelper(a: array of integer; x: integer; l,r: integer): integer;
|
|
begin
|
|
if l > r then
|
|
Result := -1
|
|
else begin
|
|
var mid := (l + r) div 2;
|
|
if x = a[mid] then
|
|
Result := mid
|
|
else if x < a[mid] then
|
|
Result := BinarySearchHelper(a, x, l, mid - 1)
|
|
else Result := BinarySearchHelper(a, x, mid + 1, r)
|
|
end;
|
|
end;
|
|
begin
|
|
Result := BinarySearchHelper(a,x,0,a.Length-1);
|
|
end;
|
|
|
|
begin
|
|
var a := ArrRandomInteger(10,1,20);
|
|
a.Sort;
|
|
a.Println;
|
|
var x := 10;
|
|
var ind := BinarySearch(a,x);
|
|
if ind >= 0 then
|
|
Println($'{x} found at index {ind}')
|
|
else Println($'{x} not found');
|
|
|
|
ind := BinarySearchRecursive(a,x);
|
|
if ind >= 0 then
|
|
Println($'{x} found at index {ind}')
|
|
else Println($'{x} not found');
|
|
|
|
x := a.RandomElement;
|
|
ind := BinarySearch(a,x);
|
|
if ind >= 0 then
|
|
Println($'{x} found at index {ind}')
|
|
else Println($'{x} not found');
|
|
|
|
ind := BinarySearchRecursive(a,x);
|
|
if ind >= 0 then
|
|
Println($'{x} found at index {ind}')
|
|
else Println($'{x} not found');
|
|
end.
|