Bài 50. Thuật toán tìm kiếm nhị phân

Tìm hiểu về thuật toán tìm kiếm nhị phân

Thuật toán tìm kiếm nhị phân là một trong các thuật toán sắp xếp được sử dụng rất nhiều trong thực tế. Trong bài viết này, chúng ta sẽ cùng đi tìm hiểu về thuật toán tìm kiếm nhị phân và ứng dụng của nó.

Tìm kiếm là một phần không thể thiếu của mọi ứng dụng, website hay phần mềm. Tính năng tìm kiếm cho phép người sử dụng nhanh chóng truy vấn và tìm kiếm các bản ghi theo mong muốn. Và một công cụ tìm kiếm nổi tiếng nhất hàng ngày chúng ta vẫn thường sử dụng đó là Google search.

Trong bài viết này, chúng ta sẽ tìm hiểu về thuật toán tìm kiếm nhị phân, một thuật toán tối ưu áp dụng đối với trường hợp dữ liệu số đã sắp xếp.

Phát biểu của thuật toán tìm kiếm nhị phân

Cho một mảng đã sắp xếp arr[] có n phần tử, chúng ta cần tìm kiếm phần tử có giá trị x trong arr[]. Thuật toán tìm kiếm nhị phân giúp chúng ta thực hiện công việc này một cách hiệu quả.

Giải thuật đơn giản nhất cho bài toán này là sử dụng linear search (tìm kiếm tuyến tính). Tuy nhiên, thuật toán này có độ phức tạp là O(n) trong trường hợp xấu nhất. Dưới đây là code minh họa cho thuật toán linear search sử dụng ngôn ngữ C/C++:

#include <stdio.h> int search(int arr[], int n, int x) {     int i;     for (i = 0; i < n; i++)         if (arr[i] == x)             return i;     return -1; }  int main() {     int arr[] = {2, 3, 4, 10, 40};     int n = sizeof(arr) / sizeof(arr[0]);     int x = 10;     int result = search(arr, n, x);     if (result != -1) {         printf("%d xuất hiện tại chỉ số %d", x, result);     } else {         printf("%d không có trong mảng", x);     }     return 0; }

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

Trong bài viết này, chúng ta sẽ giả sử mảng đang sắp xếp tăng dần. Với trường hợp mảng sắp xếp giảm dần, sau khi hiểu thuật toán, bạn đọc sẽ có thể áp dụng thuật toán tìm kiếm nhị phân một cách dễ dàng.

Do tính chất mảng đã sắp xếp, thuật toán tìm kiếm nhị phân có thể triển khai như sau:

1. Xét đoạn mảng arr[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 arr[mid+1...right].
4. Nếu arr[mid] > x, chỉ thực hiện tìm kiếm trên đoạn arr[left...mid-1].

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 với thuật toán tìm kiếm tuyến tính:

Bằng cách áp dụng thuật toán tìm kiếm nhị phân, chúng ta có thể giảm độ phức tạp trong trường hợp xấu nhất xuống còn O(log(n)).

Dành cho bạn: Sau bài học này, bạn có thể áp dụng kiến thức tìm kiếm nhị phân vào thực hành các bài tập tại Luyện Code.

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

Dưới đây là các đoạn code minh họa sử dụng các ngôn ngữ Java và C/C++ để thực hiện thuật toán tìm kiếm nhị phân. Code này sử dụng giải thuật đệ quy để triển khai.

Code minh họa C/C++ sử dụ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 - l) / 2;         // 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);         // Ngược lại, 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);     }     // Trong trường hợp 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("Không tìm thấy phần tử %d", x);     else         printf("Phần tử %d được tìm thấy tại chỉ số %d", x, result);     return 0; }

Code minh họa sử dụng đệ quy trong ngôn ngữ Java:

class BinarySearch {     int binarySearch(int arr[], int l, int r, int x) {         if (r >= l) {             int mid = l + (r - l) / 2;             // 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, gọi đệ quy tìm kiếm bên trái             if (arr[mid] > x)                 return binarySearch(arr, l, mid - 1, x);             // Ngược lại, nếu arr[mid] < x, gọi đệ quy tìm kiếm bên phải             return binarySearch(arr, mid + 1, r, x);         }         // Trong trường hợp không tìm thấy         return -1;     }      public static void main(String args[]) {         BinarySearch ob = new BinarySearch();         int arr[] = {2, 3, 4, 10, 40};         int n = arr.length;         int x = 10;         int result = ob.binarySearch(arr, 0, n - 1, x);         if (result == -1)             System.out.println("Không tìm thấy phần tử " + x);         else             System.out.println("Phần tử " + x + " được tìm thấy tại chỉ số " + result);     } }

Code khử đệ quy sử dụng C/C++:

#include <stdio.h> // Hàm tìm kiếm nhị phân sử dụng giải thuật khử đệ quy 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 - l) / 2; // Tương đương (l+r)/2 nhưng ưu điểm tránh tràn số khi l,r lớn         // 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 r         if (arr[mid] > x)             r = mid - 1;         // Nếu arr[mid] < x, cập nhật lại l         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("%d không xuất hiện trong mảng", x);     else         printf("%d xuất hiện tại chỉ số %d", x, result);     return 0; }

Dưới đây là các đoạn code minh họa sử dụng các ngôn ngữ Java và C/C++ để thực hiện thuật toán tìm kiếm nhị phân. Code này sử dụng giải thuật đệ quy để triển khai.

Code minh họa C/C++ sử dụ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 - l) / 2;         // 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);         // Ngược lại, 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);     }     // Trong trường hợp 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("Không tìm thấy phần tử %d", x);     else         printf("Phần tử %d được tìm thấy tại chỉ số %d", x, result);     return 0; }

Code minh họa sử dụng đệ quy trong ngôn ngữ Java:

class BinarySearch {     int binarySearch(int arr[], int l, int r, int x) {         if (r >= l) {             int mid = l + (r - l) / 2;             // 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, gọi đệ quy tìm kiếm bên trái             if (arr[mid] > x)                 return binarySearch(arr, l, mid - 1, x);             // Ngược lại, nếu arr[mid] < x, gọi đệ quy tìm kiếm bên phải             return binarySearch(arr, mid + 1, r, x);         }         // Trong trường hợp không tìm thấy         return -1;     }      public static void main(String args[]) {         BinarySearch ob = new BinarySearch();         int arr[] = {2, 3, 4, 10, 40};         int n = arr.length;         int x = 10;         int result = ob.binarySearch(arr, 0, n - 1, x);         if (result == -1)             System.out.println("Không tìm thấy phần tử " + x);         else             System.out.println("Phần tử " + x + " được tìm thấy tại chỉ số " + result);     } }

Code khử đệ quy sử dụng C/C++:

#include <stdio.h> // Hàm tìm kiếm nhị phân sử dụng giải thuật khử đệ quy 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 - l) / 2; // Tương đương (l+r)/2 nhưng ưu điểm tránh tràn số khi l,r lớn         // 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 r         if (arr[mid] > x)             r = mid - 1;         // Nếu arr[mid] < x, cập nhật lại l         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("%d không xuất hiện trong mảng", x);     else         printf("%d xuất hiện tại chỉ số %d", x, result);     return 0; }