Tìm hiểu thuật toán Tìm kiếm Nhị phân (Binary Search)

byHiếu Nguyễn • • 2 min read
0

Trong lĩnh vực khoa học máy tính, việc tìm kiếm là một vấn đề quan trọng và được áp dụng rộng rãi trong nhiều ứng dụng thực tế. Khi làm việc với các tập dữ liệu lớn, hiệu quả và tối ưu hóa quá trình tìm kiếm là một yếu tố then chốt. Trong bài viết này, chúng ta sẽ khám phá phương pháp tìm kiếm nhị phân - một phương pháp hiệu quả để tìm kiếm trong dữ liệu lớn.



Khái niệm thuật toán Tìm kiếm Nhị phân

Tìm kiếm nhị phân (tiếng Anh: Binary Search) là một thuật toán tìm kiếm tiên tiến dựa trên nguyên tắc chia để trị. Phương pháp này yêu cầu tập dữ liệu phải được sắp xếp theo thứ tự tăng dần hoặc giảm dần. Thuật toán tìm kiếm nhị phân tìm kiếm một phần tử cụ thể bằng cách chia tập dữ liệu làm hai và so sánh phần tử cần tìm với phần tử ở giữa. Nếu phần tử cần tìm bằng phần tử ở giữa, tìm kiếm kết thúc. Nếu không, thuật toán chỉ tiếp tục tìm kiếm trong nửa phía trước hoặc sau của tập dữ liệu, loại bỏ nửa phần không cần thiết.

Cách thức hoạt động của thuật toán tìm kiếm nhị phân

Để thực hiện tìm kiếm nhị phân, với tập dữ liệu được sắp xếp tăng dần chẳng hạn, thực hiện các bước sau:
  • Bước 1: Nhận tập dữ liệu và giá trị cần tìm.
  • Bước 2: Xác định phạm vi tìm kiếm với hai đầu trái và phải.
  • Bước 3: Kiểm tra còn phạm vi tìm kiếm hay không. Nếu còn thì tiếp tục các bước sau, không thì kết luận phần tử không tìm thấy.
  • Bước 4: Xác định phần tử đứng giữa phạm vi đó. Nếu tập dữ liệu có kích thước là số lẻ thì phần tử đứng giữa đúng ngay vị trí chính giữa, còn nếu là số chẵn thì sẽ có hai phần tử chính giữa tập dữ liệu, ta thường chọn phần tử bên trái làm phần tử đứng giữa.
  • Bước 5: So sánh phần tử đứng giữa đó với giá trị cần tìm. 
  • Bước 6: Nếu phần tử đứng giữa nhỏ hơn thì giá trị cần tìm, thì giá trị cần tìm có thể ở bên phải, thu hẹp phạm vi tìm kiếm về bên phải và tiếp tục lặp lại các bước từ bước 3 với phạm vi bắt đầu từ phần tử kề phải của phần tử đứng giữa đó.
  • Bước 7: Nếu phần tử đứng giữa lớn hơn thì giá trị cần tìm, thì giá trị cần tìm có thể ở bên trái, thu hẹp phạm vi tìm kiếm về bên trái và tiếp tục lặp lại các bước từ bước 3 với phạm vi bắt đầu từ phần tử kề trái của phần tử đứng giữa đó.
  • Bước 8: Nếu phần tử đứng giữa bằng giá trị cần tìm, thì ngừng tìm kiếm và kết luận phần tử đã được tìm thấy.
Giả sử ta có mảng arr = {9, 19, 35, 54, 56, 76, 90, 94, 110} và phần tử cần tìm là target = 54, thì thực hiện thuật toán như sau:
  • Ta xác định điểm đứng giữa phạm vi từ left qua right bằng công thức mid = (left + right) / 2 (Lưu ý phải lấy phần nguyên của phép tính này). Sau đó so sánh arr[mid] với target. Vì 56 > 54 nên ta nói 54 có thể nằm ở nửa bên trái, ta sẽ lượt bỏ tất cả phần tử từ mid tới vị trí right để tiếp tục tìm kiếm ở nửa bên trái
  • Làm tương tự bước trên, vì 19 < 54 nên thu hẹp phạm vi tìm kiếm về phía bên phải.
  • So sánh arr[mid] với target một lần nữa, vì 35 < 54 nên tiếp tục thu hẹp phạm vi tìm kiếm về phía bên phải.
  • So sánh arr[mid] với target thêm một lần nữa, vì 54 = 54 nên ta kết luận target đã được tìm thấy, ta sẽ trả về vị trí mid này.

Triển khai thuật toán

Sau đây là code triển khai thuật toán tìm kiếm nhị phân bằng những ngôn ngữ khác nhau mà bạn có thể tham khảo.

C

#include <stdio.h>

// Hàm binarySearch() lấy 3 tham số
int binarySearch(int arr[], int arrLength, int target)
{
    // Khởi tạo phạm vi ban đầu
    int left = 0;
    int right = arrLength - 1;

    while (left <= right)
    {
        // Xác định điểm đứng giữa phạm vi
        int mid = (left + right) / 2;

        // So sánh arr[mid] với target
        if (arr[mid] < target)
        {
            // Thu hẹp phạm vi về phía bên phải
            left = mid + 1; 
        }
        else if (arr[mid] > target)
        {
            // Thu hẹp phạm vi về phía bên trái
            right = mid - 1;
        }
        else
        {
            // arr[mid] == target, đã tìm thấy target
            return mid;
        }
    }
    
    // Không tìm thấy target
    return -1;
}

int main()
{
    int arr[] = {9, 19, 35, 54, 56, 76, 90, 94, 110};
    // Tính kích thước của mảng arr
    int arrLength = sizeof(arr) / sizeof(arr[0]);
    int target = 54;

    int result = binarySearch(arr, arrLength, target);

    if (result == -1)
    {
        printf("Phan tu khong tim thay trong mang.");
    }
    else
    {
        printf("Phan tu tim thay tai vi tri %d.", result);
    }
    
    // Output: 3

    return 0;
}

C++

#include <iostream>

using namespace std;

// Hàm binarySearch() lấy 3 tham số
int binarySearch(int arr[], int arrLength, int target)
{
    // Khởi tạo phạm vi ban đầu
    int left = 0;
    int right = arrLength - 1;

    while (left <= right)
    {
        // Xác định điểm đứng giữa phạm vi
        int mid = (left + right) / 2;

        // So sánh arr[mid] với target
        if (arr[mid] < target)
        {
            // Thu hẹp phạm vi về phía bên phải
            left = mid + 1; 
        }
        else if (arr[mid] > target)
        {
            // Thu hẹp phạm vi về phía bên trái
            right = mid - 1;
        }
        else
        {
            // arr[mid] == target, đã tìm thấy target
            return mid;
        }
    }
    
    // Không tìm thấy target
    return -1;
}

int main()
{
    int arr[] = {9, 19, 35, 54, 56, 76, 90, 94, 110};
    // Tính kích thước của mảng arr
    int arrLength = sizeof(arr) / sizeof(arr[0]);
    int target = 54;

    int result = binarySearch(arr, arrLength, target);

    if (result == -1)
    {
        cout << "Phan tu khong tim thay trong mang.";
    }
    else
    {
        cout << "Phan tu tim thay tai vi tri " << result;
    }
    
    // Output: 3

    return 0;
}

C#

using System;

namespace Main
{
    class Program
    {
        // Phương thức binarySearch() lấy hai tham số
        static int binarySearch(int[] arr, int target)
        {
            // Khởi tạo phạm vi ban đầu
            int left = 0;
            int right = arr.Length - 1;

            while (left <= right)
            {
                // Xác định điểm đứng giữa phạm vi
                int mid = (left + right) / 2;

                // So sánh arr[mid] với target
                if (arr[mid] < target)
                {
                    // Thu hẹp phạm vi về phía bên phải
                    left = mid + 1;
                }
                else if (arr[mid] > target)
                {
                    // Thu hẹp phạm vi về phía bên trái
                    right = mid - 1;
                }
                else
                {
                    // arr[mid] == target, đã tìm thấy target
                    return mid;
                }
            }

            // Không tìm thấy target
            return -1;
        }

        static void Main(string[] args)
        {
            int[] arr = { 9, 19, 35, 54, 56, 76, 90, 94, 110 };
            int target = 54;

            int result = binarySearch(arr, target);

            if (result == -1)
            {
                Console.WriteLine("Phan tu khong tim thay trong mang.");
            }
            else
            {
                Console.WriteLine($"Phan tu tim thay tai vi tri {result}.");
            }
            // Output: 3
        }
    }
}

Java

public class Main {
    // Phương thức binarySearch() lấy hai tham số
    public static int binarySearch(int[] arr, int target) {
        // Khởi tạo phạm vi ban đầu
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            // Xác định điểm đứng giữa phạm vi
            int mid = (left + right) / 2;

            // So sánh arr[mid] với target
            if (arr[mid] < target) {
                // Thu hẹp phạm vi về phía bên phải
                left = mid + 1;
            } else if (arr[mid] > target) {
                // Thu hẹp phạm vi về phía bên trái
                right = mid - 1;
            } else {
                // arr[mid] == target, đã tìm thấy target
                return mid;
            }
        }

        // Không tìm thấy target
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {9, 19, 35, 54, 56, 76, 90, 94, 110};
        int target = 54;

        int result = binarySearch(arr, target);

        System.out.println(result == -1? "Phan tu can tim khong co trong mang." : "Tim thay phan tu tai vi tri " + result);
        // Output: 3
    }
}

Python

# Hàm binarySearch() lấy hai tham số
def binarySearch(lst, target):
    # Khởi tạo phạm vi ban đầu
    left = 0
    right = len(lst) - 1

    while left <= right:
        # Xác định điểm đứng giữa phạm vi
        mid = (left + right) // 2

        # So sánh lst[mid] với target
        if lst[mid] < target:
            # Thu hẹp phạm vi về phía bên phải
            left = mid + 1
        elif lst[mid] > target:
            # Thu hẹp phạm vi về phía bên trái
            right = mid - 1
        else:
            # lst[mid] == target, đã tìm thấy target
            return mid
    
    # Không tìm thấy target
    return -1

lst = [9, 19, 35, 54, 56, 76, 90, 94, 110]
target = 54

result = binarySearch(lst, target)

if result == -1:
    print("Phần tử không tìm thấy trong danh sách")
else:
    print(f"Phần tử tìm thấy tại vị trí {result}")

# Output: 3

JavaScript

// Hàm binarySearch() lấy hai tham số
function binarySearch(arr, target) {
    // Khởi tạo phạm vi ban đầu
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        // Xác định điểm đứng giữa phạm vi
        let mid = Math.floor((left + right) / 2);

        // So sánh arr[mid] với target
        if (arr[mid] < target) {
            // Thu hẹp phạm vi về phía bên phải
            left = mid + 1;
        } else if (arr[mid] > target) {
            // Thu hẹp phạm vi về phía bên trái
            right = mid - 1;
        } else {
            // arr[mid] === target, đã tìm thấy target
            return mid;
        }
    }

    // Không tìm thấy target
    return -1;
}

let arr = [9, 19, 35, 54, 56, 76, 90, 94, 110];
let target = 54;

let result = binarySearch(arr, target);

if (result === -1) {
    window.alert("Phần tử không tìm thấy trong mảng.");
} else {
    window.alert("Phần tử tìm thấy tại vị trí " + result);
}
// Output: 3

Phân tích độ phức tạp về thời gian và bộ nhớ của thuật toán

Độ phức tạp về thời gian

Độ phức tạp về thời gian của tìm kiếm nhị phân là O(log n), trong đó n là số lượng phần tử trong tập dữ liệu. Điều này có nghĩa là thời gian tìm kiếm giảm theo cấp số nhân khi kích thước tập dữ liệu tăng lên. So với tìm kiếm tuyến tính (tìm hiểu tại đây), tìm kiếm nhị phân có hiệu suất cao hơn đáng kể, đặc biệt là với các tập dữ liệu lớn.

Độ phức tạp về bộ nhớ

Độ phức tạp về bộ nhớ của tìm kiếm nhị phân là O(1), tức là không yêu cầu bộ nhớ bổ sung ngoài tập dữ liệu ban đầu. Thuật toán chỉ sử dụng một số biến để lưu trữ các chỉ số và không tạo ra cấu trúc dữ liệu phức tạp.

Ưu điểm và hạn chế của thuật toán tìm kiếm nhị phân

Ưu điểm

Thuật toán tìm kiếm nhị phân có nhiều ưu điểm vượt trội hơn tìm kiếm tuyến tính như sau:
  • Nhanh và hiệu quả cao: Với độ phức tạp thời gian O(log n) đã nói trên, tìm kiếm nhị phân nhanh chóng và hiệu quả hơn rất nhiều so với tìm kiếm tuyến tính, đặc biệt là với các tập dữ liệu lớn. Đấy là vì thuật toán có thể lượt bỏ nhiều phần tử cùng lần.
  • Áp dụng cho dữ liệu được sắp xếp: Tìm kiếm nhị phân yêu cầu dữ liệu được sắp xếp theo thứ tự tăng dần hoặc giảm dần. Tuy nhiên, việc sắp xếp dữ liệu chỉ cần thực hiện một lần và sau đó có thể thực hiện nhiều tìm kiếm nhị phân trên tập dữ liệu đã sắp xếp.
  • Dễ cài đặt: Thuật toán tìm kiếm nhị phân dễ hiểu và cài đặt. Nó không yêu cầu cấu trúc dữ liệu phức tạp, chỉ cần sử dụng các phép toán so sánh đơn giản.

Hạn chế

Mặc dù tìm kiếm nhị phân có các ưu điểm ưu việt nói trên, nhưng cũng có một số nhược điểm cần lưu ý như sau:
  • Yêu cầu dữ liệu được sắp xếp: Tìm kiếm nhị phân đòi hỏi tập dữ liệu phải được sắp xếp theo thứ tự tăng dần hoặc giảm dần trước khi thực hiện. Nếu không thì thuật toán có thể đưa ra kết quả sai lệch hoàn toàn, thậm chí cho là không tồn tại dù phần tử cần tìm có trong tập dữ liệu. Nói một cách dễ hiểu hơn, các bạn hãy tưởng tượng nếu ngoài đời các bạn xem một danh sách mà không được sắp xếp theo thứ tự bảng chữ cái đi, các bạn tìm tên bạn bằng cách nào cho hiệu quả? Chắc chắn các bạn sẽ phải dò từng người một cho đến khi tìm được thôi. Trong lập trình cũng vậy, nếu dữ liệu chưa được sắp xếp thì các bạn chỉ còn một cách duy nhất để tìm kiếm là sử dụng thuật toán tìm kiếm tuyến tính nhưng không mấy nhanh và hiệu quả. Chính vì vậy, việc sắp xếp rất quan trọng, ta sẽ tìm hiểu trong blog sau.
  • Không áp dụng cho các cấu trúc dữ liệu linh hoạt: Tìm kiếm nhị phân chỉ áp dụng hiệu quả cho các cấu trúc dữ liệu tuyến tính như mảng hoặc danh sách liên kết. Đối với các cấu trúc dữ liệu phức tạp hơn như cây hay đồ thị, tìm kiếm nhị phân không phải lựa chọn tốt nhất.
  • Không thích hợp cho các tập dữ liệu có thay đổi thường xuyên: Nếu tập dữ liệu thường xuyên thay đổi (thêm, xóa, sắp xếp lại các phần tử), tìm kiếm nhị phân không phù hợp. Vì mỗi lần thay đổi dữ liệu, ta phải thực hiện lại quá trình sắp xếp, làm tốn thời gian và tài nguyên.
  • Không phù hợp cho việc tìm kiếm các phần tử không phải là giá trị duy nhất: Tìm kiếm nhị phân chỉ trả về kết quả đầu tiên tìm thấy của phần tử cần tìm. Nếu có nhiều phần tử giống nhau trong tập dữ liệu, thuật toán này không đảm bảo trả về tất cả các kết quả tương tự.
  • Không hỗ trợ tìm kiếm dựa trên các tiêu chí khác: Tìm kiếm nhị phân chỉ cho phép tìm kiếm dựa trên tiêu chí "bằng" hoặc "không bằng". Nếu muốn tìm kiếm dựa trên các tiêu chí phức tạp hơn như "lớn hơn", "nhỏ hơn" hoặc "gần đúng", ta cần sử dụng các phương pháp tìm kiếm khác.

Ứng dụng

Tìm kiếm nhị phân được áp dụng rộng rãi trong nhiều lĩnh vực, bao gồm:
  • Cơ sở dữ liệu: Khi lưu trữ dữ liệu trong cơ sở dữ liệu, tìm kiếm nhị phân được sử dụng để tìm kiếm nhanh chóng các bản ghi dựa trên các trường khóa.
  • Tìm kiếm trong mảng/số liệu: Khi làm việc với mảng hoặc danh sách được sắp xếp, tìm kiếm nhị phân giúp tìm kiếm một phần tử cụ thể một cách hiệu quả.
  • Công nghệ thông tin: Tìm kiếm nhị phân được sử dụng trong việc tìm kiếm và sắp xếp dữ liệu trong các thuật toán và ứng dụng liên quan đến xử lý dữ liệu lớn.

Kết

Tìm kiếm nhị phân là một phương pháp hiệu quả để tìm kiếm trong dữ liệu lớn. Với độ phức tạp thời gian O(log n), nó cung cấp tốc độ tìm kiếm cao và hiệu suất tốt hơn so với tìm kiếm tuyến tính. Việc sắp xếp dữ liệu trước khi áp dụng tìm kiếm nhị phân là cần thiết, nhưng cung cấp lợi ích lâu dài cho việc tìm kiếm nhanh chóng sau này. Với ưu điểm và ứng dụng rộng rãi, tìm kiếm nhị phân là một công cụ quan trọng trong việc xử lý dữ liệu và tìm kiếm thông tin trong các ứng dụng thực tế.

Tags:
4.94 / 12.043 rates

Đăng nhận xét

Mới hơn Cũ hơn