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 <bits/stdc++.h>
using namespace std;

//Đnh nghĩa hàm nhp kích thước mng:
int nhapN(){
  int n;
  do{
    cout<<"Moi nhap so luong phan tu: ";
    cin>>n;
  }while(n<1);
  return n;
}

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

//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 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;

  //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
      left = index;
    //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
      right = index;
  }

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

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

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

  cout<<"Sau khi sap xep tang dan, ta duoc ket qua:"<<endl;
  for(int i=0; i<n; i++)
    cout<<"arr["<<i<<"] = "<<arr[i]<<endl;

  float x;
  cout<<"Moi nhap so can tim: ";
  cin>>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)
    cout<<"Khong tim thay phan tu nao co gia tri "<<x<<endl;
  else
    cout<<"Tim thay phan tu tai vi tri chi so "<<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


Nếu bạn có điều thắc mắc, bạn hãy comment cho V1Study để được giải đáp.
Bài viết này được chia sẻ bởi LongDT. Nếu bạn muốn chia sẻ bài viết, bạn hãy Đăng ký làm thành viên!
« Prev
Next »
Copied !!!