Hướng dẫn binary search c++ - tìm kiếm nhị phân c ++

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à 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 nhập kích thước mảng:
void nhapN(int* n){
  do{
    printf("Moi nhap so luong phan tu: ");
    scanf("%d",&*n);
  }while(*n<1);
}

//Định nghĩa hàm nhập dữ liệu mảng:
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 sắp xếp mảng tăng dần:
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 thực hiện thuật toán tìm kiếm nhi phân
float binarySearch(float arr[], int n, float x) {

  //Trước tiên cần đặt left là chỉ số của phần
  //tử đầu tiên, right là chỉ số của phần tử
  //cuối cùng + 1
  int left=0, right=n-1;

  //Biến để lưu lại vị trí tìm thấy
  int index;

  while(left <= right) {
    // lấy vị trí chính giữa của mảng:
    index = (left + right) / 2;
  
    // nếu phần từ ở giữa mảng bằng x thì trả về index
    if (arr[index] == x)
      return index;
  
    // Nếu x lớn hơn phần tử ở giữa thì vị trí cần tìm
    // chắc chắn nằm bên phải.
    if (x > arr[index])
      // Lúc này ta thực hiện chia đôi nửa bên phải
      // bằng cách gán left là index+1
      left = index+1;
    //Ngược lại thì vị trí cần tìm chắc chẳn ở bên trái
    else
      // Lúc này ta thực hiện chia đôi nửa bên trái
      // bằng cách gán right là index-1
      right = index-1;
  }

  //Trả về -1 nếu không tìm thấy vị trí nào.
  return -1;
}

int main() {
  int i;
  int n;
  nhapN(&n); //Nhập kích thước mảng
  float arr[n];
  float x;
  nhapMang(arr,n); //Nhập liệu cho mảng

  //Tiến hành sắp xếp trước:
  //Hàm sortAsc sẽ sắp xếp mảng tăng dần
  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); //Nhập số cần tìm

  //Rồi mới 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: 10Moi nhap lieu cho mang:arr[0] = 1arr[1] = 5arr[2] = 3arr[3] = 2arr[4] = 4arr[5] = 7arr[6] = 6arr[7] = 9arr[8] = 8arr[9] = 0Sau khi sap xep tang dan, ta duoc ket qua:arr[0] = 0arr[1] = 1arr[2] = 2arr[3] = 3arr[4] = 4arr[5] = 5arr[6] = 6arr[7] = 7arr[8] = 8arr[9] = 9Moi nhap so can tim: 9Tim thay phan tu tai vi tri chi so 9
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