Chuyên đề: TÌM KIẾM

TÌM KIẾM

1. Tổng quát

Một trong những nhiệm vụ cơ bản của máy tính là tìm kiếm. Từ một cơ sở dữ liệu cho trước và một đối tượng cho trước, ta phải trả lời hai câu hỏi:
- Đối tượng có mặt trong cơ sở dữ liệu hay không?
- Nếu có thì vị trí của nó là mấy?
Để đơn giản hóa vấn đề này, ở đây chúng ta chỉ giới hạn vấn đề trong việc tìm kiếm một giá trị x nguyên xem có nằm trong một dãy số nguyên hay không?
Phương pháp tổng quát là đi so sánh cho kết quả TRUE thì việc tìm kiếm thành công.
Có nhiều thuật toán để tìm kiếm, ở đây chúng ta chỉ xét 2 thuật toán cơ bản đó là:
- Tìm tuần tự (Sequential search)
- Tìm nhị phân (Binary search).

2. Tìm kiếm tuần tự trên một dãy chưa có thứ tự

a. Thuật toán

- So sánh từng phần tử của dãy A[1..n] với giá trị x
- Trong khi đi từ phần tử đầu đến phần tử cuối của dãy:
   + Nếu tìm thấy giá trị x thì thoát ra và thông báo thứ tự của thành phần thứ i thỏa A[i]=x.
   + Nếu sau khi đã hết mà không tìm thấy thì việc tìm kiếm xem như kết thúc với kết quả là 0.

b. Lập tình Pascal

Function Tim(x:integer; a:array[1..n]of integer):word;
     var i:word;
begin
   i:=1;
   while (i<=n) and not(x=a[i]) do inc(i);
   if i>n then Tim:=0
       else Tim:=i;
end;

3. Tìm kiếm tuần tự trên một dãy đã có thứ tự

a. Thuật toán

- Thuật toán tìm tuần tự trong trường hợp xấu nhất là tìm không thấy do đó sẽ thực hiện n lần so sánh.
- Giả sử dãy A đã được sắp thứ tự tăng dần ta có thể cải tiến lại thuật toán trên để chạy nhanh hơn như sau:
   + Bắt đầu từ i=1.
   + Trong khi (i<=n) và (A[i]<x) tăng i.
   + Nếu (i<n và A[i]>x) hay (i>n) thì:
          * Không tìm thấy
       ngược lại thì:
           * Giá trị cần tìm ở vị trí thứ i.

b. Lập trình Pascal

Function Tim(x:integer; a:array[1..n]of integer):word;
     var i:word;
begin
   i:=1;
   while (i<=n) and (x>a[i]) do inc(i);
   if ((i<=n) and (a[i]>x))or (i>n) then Tim:=0
       else Tim:=i;
end;

Chú ý: 

Nếu dãy được sắp xếp giảm dần thì ta phải đảo điều kiện trong các biểu thức điều kiện sau:
while  (i<=n) and (a[i]>x)
if ((i<=n) and (a[i]<x)) or (i>n).

4. Tìm kiếm tuần tự với lính canh

a. Thuật toán

- Dùng một lính canh cụ thể là phần tử A[n+1] có thể đơn giản hóa quá trình tìm kiếm tuần tự.
- Trước khi tìm kiếm phần tử có giá trị bằng x trong đoạn dãy A[1..n]ta đặt giá trị đó tại trạm canh bằng lệnh gán:

a[n+1]:=x;

- Nhờ có lính canh nên câu lệnh lặp:

            Repeat

                    i:=i+1;

            Until a[i]:=x;

luôn luôn được kết thúc một cách tự nhiên, bởi vì trong trường hợp tìm được ta sẽ có A[i]=x với (1<=i<=n), còn trong trường hợp giá trị x không có mặt trong mảng A[1..n] thì ta vẫn có:

A[i]:=x với i:=n+1

- Việc dùng lính canh đòi hỏi mảng A phải chứa ít nhất n+1 phần tử.

b. Lập trình Pascal

   A[n+1]:=x; {đặt lính canh}

   i:=0;

   repeat

       i:=i+1;

   until a[i]:=x;

   if i<=n then write(i)

       else writeln('không tìm được');

5. Tìm kiếm nhị phân trên một mảng được sắp xếp

a. Thuật toán

- Giả sử mảng A[1..n] đã được sắp thứ tự tăng dần
- Ta chia đôi mảng A xem thành phần ở giữa có giá trị lớn hơn hay nhỏ hơn giá trị x để từ đó xác định nên tiếp tục tìm kiếm trên dãy trên hay dãy dưới. Giả sử chọn được dãy trên, tiếp tục chia đôi dãy trên để tìm kiếm cho đến khi gặp hoặc không thể chia đôi được nữa (nghĩa là không tìm thấy).
- Ta dùng 3 biến Low, High và Mid để lưu giữ chỉ số của đầu, cuối và giữa của dãy đang tìm kiếm.
- Ban đầu cho Low:= 1; High:= n;
- Trong khi High >Low thì thực hiện
   + Mid:= (Low + High) div 2
   + Nếu x> A[Mid] thì Low:= Mid + 1
             ngược lại {x<=A[Mid]}
           * Nếu x< A[Mid] thì High:=Mid-1
                   ngược lại {x=A[Mid]}
                        High:=-1
   + Nếu High:= -1 thì ta đã tìm thấy x tại vị trí thứ Mid ngược lại không tìm thấy.

b. Lập trình Pascal

Function Tim(x: integer; A: array[1..n] of integer) : word;
   var high, low, mid: integer;
begin
   low:=1; high:=n;
   while high>low do
        begin
              mid:=(high + low) div 2;

              if (a[mid]<x) then low:=mid +1
                    else if (a[mid]>x) then low:=high -1
                              else high:=-1;
        end;
   if high=-1 then Tim:= mid
           else Tim:=0;
end;