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

Tìm Kiếm Nhị Phân

Vũ Anh Quân

Thuật toán tìm nhị phân hay còn gọi là phương pháp chia đôi được ápdụng rất nhiều trong

tin học. Phương pháp này làm giảm được nhiều thời gian tìmkiếm, giúp chương trình chạy

nhanh hơn. Sau đây tôi xin giới thiệu một số bàitoán sử dụng phương pháp trên.

Bàitoán 1: Xác định vị trí của phần tử X trong bảng liệt kê sắpxếp tăng các phần tử phân

biệt A1, A2,.., AN.(A1< A2<... < AN)

Bài giải: Chia đôi bảng liệt kê A1, A2,.., AN thành 2 bảng liệt kê:

A1, A2,.., Am và Am+1,Am+2,.., AN (trong đó m=(N+1) div 2).

+Nếu X>Am thìtìm kiếm trên bảng liệt kê Am+1, Am+2,.., AN.

+Nếu X<=Am thìtìm kiếm trên bảng liệt kê A1, A2,.., Am.

Quá trình trên được thực hiện cho tới khi bảng liệt kêchỉ còn một phần tử. Sau đó so sánh

X với số hạng này.

Mô tả thuật toán tìm kiếm nhị phân.

Function VT(X: integer): integer ;

Var

i, j, m : integer;

Begin

i:=1; j:=N;

while i<>

begin

m:= (i+j) div 2;

if X>A[m] then i:=m+1 else i:=m;

end;