Trang chủLập trìnhCTDL & Thuật toánThuật toán tìm kiếm nhị phân trong C/C++

Thuật toán tìm kiếm nhị phân trong C/C++

Thuật toán tìm kiếm nhị phân là một trong các thuật toán tìm kiếm được sử dụng rất nhiều trong thực tế. Hãy cùng blog TUICOCACH.COM đi tìm hiểu thuật toán tìm kiếm này trong bài viết hôm nay nhé.

Ý tưởng của thuật toán tìm kiếm nhị phân

Giả sử bạn đang có một mảng A bao gồm n phần tử, bạn đang cần tìm kiếm phần tử ở x.

Giải thuật đơn giản nhất cho bài toán tìm kiếm này là sử dụng linear search(tìm kiếm tuyến tính hay gọi là tìm kiếm tuần tự). Tức là bạn sẽ phải đi qua từng phần tử của mảng để đối chiếu với x cần tìm. Thuật toán này trong trường hợp xấu nhất cho độ phức tạp là O(n).

Vậy bạn có đặt ra câu hỏi, có thuật toán nào tìm kiếm nhanh và tối ưu hơn không? Câu trả lời đó là thuật toán tìm kiếm nhị phân(Binary search).

Ý tưởng của thuật toán tìm kiếm nhị phân đó là mỗi lần thực hiện chúng ta sẽ chia mảng ra làm 2 phần, lấy ra phần tử y ở chính giữa và đem phần tử này so sánh với phần tử x cần tìm. Nếu y=x tìm thấy phần tử, ngược lại tiếp tục thực hiện chia mảng đối với mảng con bên trái hoặc mảng con bên phải tùy thuộc vào y<x hay y>x. Thuật toán kết thúc khi tìm thấy phần tử hoặc mảng con không thể chia nhỏ.

Theo như ý tưởng thuật toán ta sẽ lấy ra phần tử y là phần tử chốt và so sánh phần tử chốt này với x cần tìm, mục đích của việc này là kiểm tra xem x nằm ở bên phải hay bên trái mảng so với phần tử chốt là Y. Tức là thuật toán tìm kiếm nhị phân chỉ có thể thực hiện trên mảng đã được sắp xếp(sắp xếp tăng dần hoặc giảm dần), và đây cũng chính là một nhược điểm của thuật toán tìm kiếm này.

Tiếp tục giả sử mảng A ở trên đã được sắp xếp tăng dần, ta có thể mô tả các bước thực hiện thuật toán như sau:

  1. Xét đoạn mảng A[left…right] cần tìm kiếm phần tử x. Ta so sánh x với phần tử ở vị trí giữa của mảng(mid = (left + right)/2). Nếu:
  2. Nếu phần tử arr[mid] = x. Kết luận và thoát chương trình.
  3. Nếu arr[mid] < x. Chỉ thực hiện tìm kiếm trên đoạn A[mid+1…right].
  4. Nếu arr[mid] > x. Chỉ thực hiện tìm kiếm trên đoạn A[left…mid-1].

Nếu vẫn chưa thể hình dung, hình ảnh dưới đây mô phỏng quá trình thực hiện của thuật toán tìm kiếm nhị phân và so sánh thuật toán tìm kiếm nhị phân với thuật toán tìm kiếm tuyến tính.

So sánh thuật toán tìm kiếm nhị phân và thuật toán tìm kiếm tuần tự
So sánh thuật toán tìm kiếm nhị phân và thuật toán tìm kiếm tuần tự(Nguồn ảnh: Mathwarehouse.com)

Với thuật toán tìm kiếm nhị phân độ phức tạp cho trường hợp xấu nhất chỉ là O(log(n)).

Minh họa code cho thuật toán tìm kiếm nhị phân

Minh họa thuật toán bằng Đệ quy

#include <stdio.h>
 
// Hàm tìm kiếm nhị phân sử dụng giải thuật đệ quy
int binarySearch(int arr[], int l, int r, int x) {
  if (r >= l) {
    int mid =  (l+r)/2; //vị trí ở giữa
 
    // Nếu arr[mid] = x, trả về chỉ số và kết thúc.
    if (arr[mid] == x)
      return mid;
 
    // Nếu arr[mid] > x, thực hiện tìm kiếm nửa trái của mảng
    if (arr[mid] > x)
      return binarySearch(arr, l, mid - 1, x);
 
    // Nếu arr[mid] < x, thực hiện tìm kiếm nửa phải của mảng
    return binarySearch(arr, mid + 1, r, x);
  }
 
  // Nếu không tìm thấy
  return -1;
}
 
int main(void) {
  int arr[] = {2, 3, 4, 10, 40};
  int n = sizeof(arr) / sizeof(arr[0]);
  int x = 10;
  int result = binarySearch(arr, 0, n - 1, x);
  if (result == -1)
    printf("Khong tim thay phan tu %d trong mang",x);
  else
    printf("%d xuat hien tai chi so %d", x, result);
  return 0;
}

Minh họa thuật toán bằng vòng lặp

#include <stdio.h>

// Hàm tìm kiếm nhị phân 
int binarySearch(int arr[], int n, int x) {
  int r = n - 1; // chỉ số phần tử cuối
  int l = 0; // Chỉ số phần tử đầu tiên
  while (r >= l) {
    int mid = (l+r)/2; //vị trí ở giữa
 
    // Nếu arr[mid] = x, trả về chỉ số và kết thúc.
    if (arr[mid] == x)
      return mid;
 
    // Nếu arr[mid] > x, cập nhật lại right
    if (arr[mid] > x)
      r = mid - 1;
    // Nếu arr[mid] < x, cập nhật lại left
    if (arr[mid] < x)
      l = mid + 1;
  }
 
  // Nếu không tìm thấy
  return -1;
}
 
int main(void) {
  int arr[] = {2,3,4,10,40};
  int n = sizeof(arr) / sizeof(arr[0]);
  int x = 10;
  int result = binarySearch(arr, n, x);
  if (result == -1)
     printf("Khong tim thay phan tu %d trong mang",x);
  else
    printf("%d xuat hien tai chi so %d", x, result);
  return 0;
}

Cảm ơn bạn đã theo dõi bài viết! Chúc học tốt!

XEM THÊM
Thuật toán đếm số lượng chữ số của số nguyên dương n bằng C / C++
Thuật toán sắp xếp nhanh (Quick Sort)
Thuật toán sắp xếp trộn (Merge Sort)
Một số chương trình xây dựng trên Graphics C/C++
Hướng dẫn cài đặt thư viện Graphics trên IDE Devc++
0 0 Phiếu bình chọn
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?


0
Giáo sư! có thể ném gạch bên dưới nhé!x
()
x