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.