Thuật Toán Tìm Kiếm Nhị Phân (Binary Search) – Giải Thuật Hiệu Quả và Ứng Dụng

Tìm kiếm nhị phân, hay binary search, là một thuật toán tìm kiếm cực kỳ hiệu quả, được sử dụng rộng rãi trong khoa học máy tính. Thuật toán này đặc biệt hữu ích khi cần tìm kiếm một phần tử trong một mảng đã được sắp xếp (tăng dần hoặc giảm dần). So với tìm kiếm tuyến tính, tìm kiếm nhị phân có độ phức tạp thời gian tốt hơn đáng kể, giúp tăng tốc quá trình tìm kiếm, đặc biệt với dữ liệu lớn.

Hình ảnh minh họa quá trình tìm kiếm nhị phân, chia nhỏ mảng để tìm kiếm hiệu quả hơn.

Nguyên Lý Hoạt Động của Thuật Toán Nhị Phân

Thuật toán tìm kiếm nhị phân hoạt động dựa trên nguyên tắc “chia để trị”. Nó liên tục chia đôi khoảng tìm kiếm cho đến khi tìm thấy phần tử cần tìm hoặc khoảng tìm kiếm trở nên rỗng. Dưới đây là các bước thực hiện thuật toán:

1. Điều kiện tiên quyết: Mảng cần tìm kiếm phải được sắp xếp theo thứ tự (tăng dần hoặc giảm dần).
2. Xác định khoảng tìm kiếm: Ban đầu, khoảng tìm kiếm là toàn bộ mảng. Chỉ số đầu tiên là L (left) và chỉ số cuối cùng là R (right).
3. Tìm phần tử ở giữa: Tính chỉ số của phần tử ở giữa khoảng tìm kiếm: M = (L + R) / 2.
4. So sánh: So sánh giá trị của phần tử ở giữa (A[M]) với giá trị cần tìm (X).
   • Nếu A[M] == X: Tìm thấy phần tử cần tìm. Trả về chỉ số M.
   • Nếu A[M] > X: Phần tử cần tìm (nếu có) nằm ở nửa bên trái của khoảng tìm kiếm. Cập nhật R = M - 1.
   • Nếu A[M] < X: Phần tử cần tìm (nếu có) nằm ở nửa bên phải của khoảng tìm kiếm. Cập nhật L = M + 1.
5. Lặp lại: Lặp lại các bước 3 và 4 cho đến khi tìm thấy phần tử hoặc L > R (khoảng tìm kiếm rỗng, nghĩa là không tìm thấy phần tử).

Với mỗi lần lặp, kích thước khoảng tìm kiếm giảm đi một nửa, giúp thuật toán đạt được hiệu quả cao. Ví dụ, trong một mảng có một tỷ phần tử, số lần tìm kiếm tối đa chỉ là khoảng 30.

Trường hợp tìm thấy phần tử ở giữa bằng giá trị cần tìm, thuật toán kết thúc.

Hình ảnh minh họa trạng thái tìm thấy phần tử cần tìm ở vị trí giữa khoảng tìm kiếm.

Trường hợp phần tử ở giữa nhỏ hơn giá trị cần tìm, ta thu hẹp phạm vi tìm kiếm sang nửa bên phải.

Hình ảnh minh họa việc loại bỏ nửa trái của mảng khi giá trị cần tìm lớn hơn giá trị ở giữa.

Trường hợp phần tử ở giữa lớn hơn giá trị cần tìm, ta thu hẹp phạm vi tìm kiếm sang nửa bên trái.

Hình ảnh minh họa việc loại bỏ nửa phải của mảng khi giá trị cần tìm nhỏ hơn giá trị ở giữa.

Cài Đặt Thuật Toán Tìm Kiếm Nhị Phân (Binary Search) bằng C

#include <stdio.h>

int binary_search(int a[], int n, int x) {
  int l = 0, r = n - 1; // Khởi tạo left, right
  while (l <= r) {
    int m = (l + r) / 2; // Tính chỉ số phần tử ở giữa

    if (a[m] == x) {
      return 1; // Tìm thấy
    } else if (a[m] < x) {
      l = m + 1; // Tìm kiếm ở bên phải
    } else {
      r = m - 1; // Tìm kiếm ở bên trái
    }
  }
  return 0; // Không tìm thấy
}

int main() {
  int n = 12, x = 24, y = 6;
  int a[12] = {1, 2, 3, 4, 5, 5, 7, 9, 13, 24, 27, 28};

  if (binary_search(a, n, x)) {
    printf("FOUNDn");
  } else {
    printf("NOT FOUNDn");
  }

  if (binary_search(a, n, y)) {
    printf("FOUNDn");
  } else {
    printf("NOT FOUNDn");
  }
  return 0;
}

Giải thích code:

• Hàm binary_search(int a[], int n, int x):
  • a[]: Mảng đã sắp xếp.
  • n: Số lượng phần tử trong mảng.
  • x: Giá trị cần tìm.
  • Hàm trả về 1 nếu tìm thấy x, và 0 nếu không tìm thấy.
• l và r: Biến lưu chỉ số đầu và cuối của khoảng tìm kiếm.
• while (l <= r): Vòng lặp tiếp tục cho đến khi khoảng tìm kiếm không còn.
• m = (l + r) / 2: Tính chỉ số phần tử ở giữa.
• Các lệnh if...else if...else: So sánh a[m] với x và cập nhật l hoặc r tương ứng.
• Hàm main(): Khởi tạo mảng, giá trị cần tìm, và gọi hàm binary_search() để tìm kiếm.

Ví dụ:

• Tìm X = 3 trong mảng A[] = {1, 1, 3, 4, 5, 8, 9, 12, 21, 32}. Thuật toán sẽ tìm thấy X ở vị trí thứ 2 (chỉ số 2).
• Tìm X = 2 trong mảng A[] = {1, 1, 3, 4, 5, 8, 9, 12, 21, 32}. Thuật toán sẽ không tìm thấy X vì 2 không có trong mảng.

Các Bài Toán Tìm Kiếm Nhị Phân Biến Thể

Ngoài việc tìm kiếm một giá trị cụ thể, thuật toán tìm kiếm nhị phân còn có thể được biến đổi để giải quyết nhiều bài toán khác:

• Tìm vị trí đầu tiên của phần tử X trong mảng đã sắp xếp tăng dần: Khi tìm thấy X, tiếp tục tìm kiếm ở nửa bên trái để tìm vị trí đầu tiên.
• Tìm vị trí cuối cùng của phần tử X trong mảng đã sắp xếp tăng dần: Khi tìm thấy X, tiếp tục tìm kiếm ở nửa bên phải để tìm vị trí cuối cùng.
• Tìm vị trí đầu tiên của phần tử lớn hơn hoặc bằng X trong mảng đã sắp xếp tăng dần: Khi tìm thấy phần tử lớn hơn hoặc bằng X, tiếp tục tìm kiếm ở nửa bên trái.

Ví dụ Code cho Bài Toán Tìm Vị Trí Đầu Tiên

#include <stdio.h>

int firstPos(int a[], int n, int x) {
  int l = 0, r = n - 1;
  int pos = -1; // Cập nhật kết quả

  while (l <= r) {
    int m = (l + r) / 2;
    if (a[m] == x) {
      pos = m; // Lưu lại
      r = m - 1; // Tìm thêm bên trái
    } else if (a[m] < x) {
      l = m + 1; // Tìm kiếm bên phải
    } else {
      r = m - 1; // Tìm kiếm bên trái
    }
  }
  return pos;
}

int main() {
  int n = 10, x = 3;
  int a[10] = {1, 1, 2, 2, 3, 3, 3, 5, 7, 9};
  int res = firstPos(a, n, x);

  if (res == -1) {
    printf("%d khong xuat hien trong mangn", x);
  } else {
    printf("Vi tri dau tien cua %d trong mang : %dn", x, res);
  }

  return 0;
}

Trong ví dụ này, với mảng a[] = {1, 1, 2, 2, 3, 3, 3, 5, 7, 9} và x = 3, kết quả sẽ là vị trí đầu tiên của 3 là 4.

Kết Luận

Thuật toán tìm kiếm nhị phân là một công cụ mạnh mẽ và hiệu quả để tìm kiếm trong dữ liệu đã được sắp xếp. Việc hiểu rõ nguyên lý hoạt động và các biến thể của thuật toán này là rất quan trọng đối với bất kỳ lập trình viên nào. Bằng cách tận dụng sức mạnh của tìm kiếm nhị phân, bạn có thể tối ưu hóa hiệu suất của các ứng dụng và giải quyết các bài toán tìm kiếm một cách hiệu quả hơn.