[Thuật toán] Tìm kiếm nhị phân:

Là phương pháp tìm kiếm phổ biến, dựa trên dãy đã sắp xếp thứ tự. Nội dung của giải thuật này là : lấy khoá X cần tìm so sánh với phần tử ở giữa dãy , với vị trí phần tử ở giữa được xác định là mid = (hight+low)/2, trong đó cận dưới low=0, cận trên hight= n-1. Vì dãy đã sắp xếp nên có các trường hợp sau xảy ra: 
nếu X= A[mid] thì cho ra kết quả (cần tìm X trong dãy A[i])
nếu X < A[mid] => X thuộc khoảng [A[low];A[mid-1] ] lại tiếp tục tìm kiếm nhị phân X trong dãy từ A[low]-> A[mid -1]
Nếu X> A[mid]=> X thuộc khoảng [A[mid+1], A[hight]], lại tiếp tục tìm kiếm nhị phân X trong dãy từ A[mid + 1], A[hight]
Quá trình tìm cho tới khi tìm ra X hoặc không tìm được X trong dãy

Có thể viết thuật toán tìm kiếm nhị phân theo vòng lặp hoặc theo đệ quy đều được.
Ta sẽ viết luôn thủ tục hàm tìm kiếm nhị phân theo hai cách:
Hàm tìm kiếm nhị phân mà chúng ta viết là : 
Binary_Search(Usertype *A, Usertype X, int n);
Trong đó: Usertype là cấu trúc dữ liệu mà ta cần tìm kiếm, có thể là các kiểu đơn giản có sẵn: int, long , float, doublle., char… hoặc các kiểu do người dùng định nghĩa, có thể là một cấu trúc nào đó (ví dụ như Struct SinhVien, SoPhuc….)
Mảng A có n phần tử đã được sắp xếp. Do đó trước khi thực hiện thao tác tìm kiếm thì chúng ta phải thực hiện thao tác sắp xếp dãy đã.

Viết dưới dạng vòng lặp : 

int Binary_Search(Usertype *A, Usertype X, int n) // hàm trả về là vị trí của X trong dãy
{

2.     int mid,low=o,hight=n-1;
3.     while(low<=hight) // lap neu can duoi van nho hon can tren
4.        {
5.     mid=(low+hight)/2;  //xác định vị trí phần tử ở giữa
6.     if(X>A[mid]) low=mid+1;      // X thuộc [mid+1,hight]
7.             else        if(X<A[mid]) hight=mid-1;   // X thuộc đoạn [low,mid-1]
8.     else   return(mid); //trả về vị trí của X trong dãy
9.    }
10.         return(-1); // nếu X không thuộc dãy thì trả về giá trị của hàm là -1
11. }

Viết dưới dạng hàm đệ quy:

C Code:

1. int Binary_Search(Usertype *A, Usertype X, int i,int j)  // hàm trả về là vị trí của X trong dãy
2. {
3.     int mid=(i+j)/2;
4.     if(X>A[mid]&&i<mid)
5.         return(Binary_Search(A,X,mid+1,j));
6.     else if(X<A[mid]&&j>mid)
7.         return(Binary_Search(A,X,i,mid-1));
8.     else if(X==A[mid])
9.         return(mid);
10.     return(-1); // tra lai gia tri la -1 nếu không tìm thấy X
11. }

Chương trình cài đặt thuật toán cho tìm kiếm nhị phân một số nguyên trong dãy như sau:

C Code:

1. #include    <stdio.h>
2. #include    <conio.h>
3. #include    <stdlib.h>
4. #include    <alloc.h>
5. #include    <dos.h>
6. int Binary_Search( int *, int, int);
7. void Bubble(int *, int);
8. void Init(int *, int);
10. int Binary_Search( int *A, int X, int n) {
11.     int mid, low = 0, hight = n-1;
12.     while (low<=hight){
13.         mid = (low +hight)/2;
14.         if (X >A[mid] ) low = mid +1;
15.         else if (X<A[mid] ) hight = mid -1;
16.         else    return (mid);
17.     }
18.     return(-1);
19. }
20. void Init(int *A, int n){
21.     int i;
22.     printf("\n Tao lap day so:");
23.     for (i=0; i<n;i++){
24.         A[i]=random(1000);
25.         printf("%5d",A[i]);
26.     }
27.     delay(1000);
28. }
29. void Bubble(int *A, int n){
30.     register i,j,temp;
31.     for (i=1; i<n; i++){
32.         for (j=n-1; j>=i;j--){
33.             if (A[j-1]>A[j]){
34.                 temp=A[j-1];
35.                 A[j-1]=A[j];
36.                 A[j]=temp;
37.             }
38.         }
39.         printf("\n Ket qua lan:%d", i);
40.         In(A,n);
41.     }
42. }
43. void In(int *A, int n){
44.     register int i;
45.     for(i=0;i<n;i++)
46.         printf("%5d",A[i]);
47.     delay(1000);
48. }
49. void main(void){
50.     int *A,n, X, k;clrscr();
51.     printf("\n Nhap n="); scanf("%d",&n);
52.     printf(“\n Sè cÇn t×m X=”); scanf(“%d”,&X);
53.     A=(int *) malloc(n*sizeof(int));
54.     Init(A,n);Bubble(A,n); k= Binary_Search(A, X, n);
55.     if ( k>0)
56.         printf (“\n %d ë vÞ trÝ sè %d”, X, k);
57.     else
58.         printf(“\n %d kh«ng thuéc d·y”);
59.     getch();
60.     free(A);
61. }

Download code tìm kiếm nhị phân miễn phí