Thuật toán tìm kiếm nhị phân trong Pascal

Dưới đây là một ví dụ về thuật toán tìm kiếm nhị phân trong Pascal:

function binarySearch(arr: array of integer; x: integer): integer;
var
  left, right, mid: integer;
begin
  left := 0;
  right := length(arr) - 1;
  while left <= right do
  begin
    mid := (left + right) div 2;
    if arr[mid] = x then
    begin
      Result := mid;
      exit;
    end
    else if arr[mid] < x then
      left := mid + 1
    else
      right := mid - 1;
  end;
  Result := -1; // x không tồn tại trong mảng
end;

Trong thuật toán này, arr là một mảng đã được sắp xếp theo thứ tự tăng dần và x là phần tử cần tìm. Ta sử dụng ba biến left, right và mid để lưu vị trí bắt đầu, kết thúc và giữa của mảng con đang xem xét. Trong vòng lặp, ta tiến hành so sánh giá trị tại vị trí mid với x. Nếu bằng nhau, ta trả về vị trí mid. Nếu giá trị tại mid nhỏ hơn x, ta chỉnh left để loại bỏ một nửa bên trái của mảng con đang xem xét. Ngược lại, ta chỉnh right để loại bỏ một nửa bên phải của mảng con đang xem xét. Nếu không tìm thấy x sau khi xét hết mảng, ta trả về -1 để báo hiệu rằng x không tồn tại trong mảng.

Chú ý rằng trong ví dụ này, ta sử dụng từ khóa Result để trả về kết quả của hàm binarySearch. Ta có thể thay thế từ khóa này bằng cách sử dụng tên hàm làm biến kết quả, ví dụ binarySearch := mid.

Đây là một ví dụ về cách sử dụng thuật toán tìm kiếm nhị phân trong Pascal:

program BinarySearchExample;

function binarySearch(arr: array of integer; x: integer): integer;
var
  left, right, mid: integer;
begin
  left := 0;
  right := length(arr) - 1;
  while left <= right do
  begin
    mid := (left + right) div 2;
    if arr[mid] = x then
    begin
      Result := mid;
      exit;
    end
    else if arr[mid] < x then
      left := mid + 1
    else
      right := mid - 1;
  end;
  Result := -1; // x không tồn tại trong mảng
end;

var
  arr: array[0..7] of integer = (3, 5, 8, 12, 14, 17, 21, 39);
  x, index: integer;
begin
  writeln('Nhap so can tim:');
  readln(x);
  index := binarySearch(arr, x);
  if index = -1 then
    writeln('Khong tim thay so trong mang')
  else
    writeln('So can tim o vi tri ', index);
end.

Trong ví dụ này, ta định nghĩa một mảng arr chứa các phần tử đã được sắp xếp theo thứ tự tăng dần và một số x cần tìm trong mảng. Ta gọi hàm binarySearch để tìm vị trí của x trong arr. Kết quả trả về là vị trí của x trong mảng hoặc -1 nếu x không tồn tại trong mảng. Ta sử dụng biến index để lưu trữ kết quả tìm kiếm và hiển thị thông báo phù hợp cho người dùng.