Lập trình C: Tìm kiếm nhị phân (Binary Search)


Đăng ký nhận thông báo về những video mới nhất

Tổng quan

Tìm kiếm nhị phân là một trong những thuật toán khá phổ biến để có thể tìm một phần tử nào đó trong mảng.

Lưu ý: Thuật toán chỉ có tác dụng khi mảng đã được sắp xếp theo một trật tự nào đó (tăng hoặc giảm).

So với thuật toán tìm kiếm tuần tự (linear search) thì độ phức tạp thuật toán của tìm kiếm nhị phân nhỏ hơn khá nhiều. Vậy nên, tìm kiếm nhị phân có thể áp dụng cho mảng dữ liệu lớn.

Cách thức triển khai thuật toán tìm kiếm nhị phân như sau:

Cần tìm phần tử x nào đó có tồn tại trong mảng arr gồm n phần tử thì trước tiên ta tiến hành so sánh x với phần tử nằm ở vị trí chính giữa của mảng (vị trí index = n/2):

  • nếu x bằng arr[index] thì trả về index và kết thúc tìm kiếm,
  • nếu x < arr[index] thì chắc chắn x sẽ nằm ở phía bên trái của index tức là từ arr[0] đến arr[index-1],
  • nếu x > arr[mid] thì chắc chắn x sẽ nằm ở phía bên phải của index tức là từ arr[mid+1] đến arr[n-1].
  • tiếp tục thực hiện chia đôi các khoảng tìm kiếm tới khi nào tìm thấy được vị trí của x trong mảng hoặc khi đã duyệt hết mảng.

Độ phực tạp của thụâ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(log2n) và trung bình là O(log2n).

Ví dụ

Hãy nhập vào mảng arr gồm n phần tử thực, sau đó nhập vào một số x rồi tìm xem mảng arr có phần tử nào có giá trị = x hay không.

#include<stdio.h>

//Đnh nghĩa hàm nhp kích thước mng:
void nhapN(int* n){
  do{
    printf("Moi nhap so luong phan tu: ");
    scanf("%d",&*n);
  }while(*n<1);
}

//Đnh nghĩa hàm nhp d liu mng:
void nhapMang(float arr[],int n){
  int i;
  printf("Moi nhap lieu cho mang:\n");
  for(i=0; i<n; i++){
    printf("arr[%d] = ",i);
    scanf("%f",&arr[i]);
  }
}

//Đnh nghĩa hàm sp xếp mng tăng dn:
void sortAsc(float arr[],int n){
  int i,j;
  float tg;
  for(i=0; i<n-1; i++){
    for(j=n-1; j>i; j--){
      if(arr[i]>arr[j]){
        tg=arr[i];
        arr[i]=arr[j];
        arr[j]=tg;
      }
    }
  }
}

//Hàm thc hin thut toán tìm kiếm nhi phân
float binarySearch(float arr[], int n, float x) {

  //Trước tiên cn đt left là ch s ca phn
  //t đu tiên, right là ch s ca phn t  //cui cùng + 1
  int left=0, right=n-1;

  //Biến đ lưu li v trí tìm thy
  int index;

  while(left <= right) {
    // ly v trí chính gia ca mng:
    index = (left + right) / 2;
  
    // nếu phn từ ở gia mng bng x thì tr v index
    if (arr[index] == x)
      return index;
  
    // Nếu x ln hơn phn tử ở gia thì v trí cn tìm
    // chc chn nm bên phi.
    if (x > arr[index])
      // Lúc này ta thc hin chia đôi na bên phi
      // bng cách gán left là index+1
      left = index+1;
    //Ngược li thì v trí cn tìm chc chn  bên trái
    else
      // Lúc này ta thc hin chia đôi na bên trái
      // bng cách gán right là index-1
      right = index-1;
  }

  //Tr v -1 nếu không tìm thy v trí nào.
  return -1;
}

int main() {
  int i;
  int n;
  nhapN(&n); //Nhp kích thước mng
  float arr[n];
  float x;
  nhapMang(arr,n); //Nhp liu cho mng

  //Tiến hành sp xếp trước:
  //Hàm sortAsc s sp xếp mng tăng dn
  sortAsc(arr,n);

  printf("Sau khi sap xep tang dan, ta duoc ket qua:");
  for(i=0; i<n; i++)
    printf("\narr[%d] = %g",i,arr[i]);

  printf("\nMoi nhap so can tim: ");
  scanf("%f",&x); //Nhp s cn tìm

  //Ri mi tiến hành tìm kiếm nh phân
  int index = binarySearch(arr, n, x);

  if(index==-1)
    printf("Khong tim thay phan tu nao co gia tri %g",x);
  else
    printf("Tim thay phan tu tai vi tri chi so %d.",index);

  return 0;
}

Dưới đây là một kết quả demo:

Moi nhap so luong phan tu: 10
Moi nhap lieu cho mang:
arr[0] = 1
arr[1] = 5
arr[2] = 3
arr[3] = 2
arr[4] = 4
arr[5] = 7
arr[6] = 6
arr[7] = 9
arr[8] = 8
arr[9] = 0
Sau khi sap xep tang dan, ta duoc ket qua:
arr[0] = 0
arr[1] = 1
arr[2] = 2
arr[3] = 3
arr[4] = 4
arr[5] = 5
arr[6] = 6
arr[7] = 7
arr[8] = 8
arr[9] = 9
Moi nhap so can tim: 9
Tim thay phan tu tai vi tri chi so 9


Bài viết này được đóng góp bởi LongDT. Nếu bạn thích V1Study và muốn đóng góp, bạn gửi bài viết về địa chỉ [email protected] hoặc gửi vào Zalo 0986.589.410. Bài viết của bạn sẽ xuất hiện sau khi được duyệt và bạn có thể trợ giúp những người học khác.
« Prev
Next »
Copied !!!