Phương pháp tìm kiếm nhị phân

Phương pháp tìm kiếm nhị phân được áp dụng trên dãy khóa đã sắp thứ tự. Tức là K[1] ≤ K[2] ≤ ... ≤ K[n]

Nội dung thuật toán

Giả sử cần tìm X trong đoạn K[L ... R] (L ≤ R), trước hết ta xét khóa nằm giữa đoạn K[Mid] với Mid = (L + R) div 2;

• Nếu K[Mid] < X nghĩa là đoạn K[L ... Mid] chứa toàn khóa < X, khi đó ta tiến hành tìm kiếm X trên đoạn K[Mid+1 ... R]

• Nếu K[Mid] > X nghĩa là đoạn K[L ... Mid] chứa toàn khóa > X, khi đó ta tiến hành tìm kiếm X trên đoạn K[L ... Mid - 1]

• Nếu K[Mid] = X thì tìm kiếm thành công (kết thúc quá trình tìm kiếm).

Quá trình tìm kiếm sẽ thất bại nếu một bước nào đó đoạn tìm kiếm là rỗng tức là L > R

Nội dung chương trình

Function TK_NhiPhan(X: Key): Longint;

Var L,R,Mid: Longint;

Begin

L := 1; R := N;

While (L <= R) do

Begin

Mid := (L + R) div 2;

if K[Mid] = X then exit(Mid);

if K[Mid] < X then L := Mid + 1

else R := Mid – 1;

End;

exit(0);

End;

Độ phức tạp thuật toán.

Người ta chứng minh được độ phức tạp tính toán của thuật toán tìm kiếm nhị phân trong trường hợp tốt nhất là O(1), trong trường hợp xấu nhất là O(logN). Tuy nhiên không nên quên rằng trước khi sử dụng phương pháp tìm kiếm nhị phân thì dãy khóa phải được sắp xếp, tức là thời gian chi phí cho việc sắp xếp phải được tính đến.