program BinarySearchAverageSteps;

const
maxSize = 32;
range = 100;
iterations = 1000;

type
TArray = array[1..maxSize] of Integer;

var
arr: TArray;
totalSteps: Integer;
i, j, num, steps: Integer;

function BinarySearch(arr: TArray; target: Integer): Integer;
var
left, right, mid: Integer;
begin
left := 1;
right := maxSize;
result := 0;

while left <= right do
begin
mid := (left + right) div 2;
Inc(result);

if arr[mid] = target then
Exit
else if arr[mid] < target then
left := mid + 1
else
right := mid - 1;

end;
end;

begin
Randomize;

totalSteps := 0;

for i := 1 to iterations do
begin
for j := 1 to maxSize do
arr[j] := Random(range);

// Sort the array
for j := 1 to maxSize do
begin
for num := j + 1 to maxSize do
begin
if arr[j] > arr[num] then
begin
steps := arr[j];
arr[j] := arr[num];
arr[num] := steps;
end;
end;
end;
// Binary search for a random number
num := Random(range);
steps := BinarySearch(arr, num);
totalSteps := totalSteps + steps;

end;

writeln('Average number of steps in binary search:', totalSteps div iterations);
end.