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

//Đị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