Thuật toán tìm kiếm nhị phân (Binary Search)

Tìm kiếm nhị phân (Binary Search) là một thuật toán tìm kiếm hiệu quả được sử dụng để tìm kiếm một giá trị trong một danh sách đã được sắp xếp (thường là một mảng).

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

Thuật toán này hoạt động bằng cách chia đôi danh sách và so sánh giá trị cần tìm với giá trị ở giữa danh sách.

1. Nếu giá trị cần tìm bằng giá trị ở giữa, thuật toán kết thúc.
2. Nếu không, xác định xem giá trị cần tìm có thể nằm ở nửa trên hoặc nửa dưới của danh sách và lặp lại quá trình trên phần danh sách con đó.

Thuật toán tìm kiếm nhị phân hoạt động rất nhanh và hiệu quả với danh sách đã được sắp xếp, với độ phức tạp thời gian là O(log n), trong đó “n” là số phần tử trong danh sách. Điều này làm cho nó trở thành một trong những thuật toán tìm kiếm phổ biến và quan trọng trong lập trình và khoa học máy tính.

Ví dụ thuật toán tìm kiếm nhị phân bằng Java

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
        int target = 12;

        int result = binarySearch(arr, target);

        if (result == -1) {
            System.out.println("Không tìm thấy " + target + " trong mảng.");
        } else {
            System.out.println(target + " được tìm thấy tại vị trí " + result);
        }
    }

    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                return mid;  // Trả về chỉ số của phần tử nếu tìm thấy
            }

            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1; // Trả về -1 nếu không tìm thấy
    }
}

Chạy thử code tại đây: https://www.jdoodle.com/online-java-compiler/

Trong ví dụ này, chúng ta sử dụng hàm binarySearch để tìm kiếm một số nguyên target trong mảng đã được sắp xếp arr. Hàm binarySearch sử dụng một vòng lặp while để tìm kiếm giá trị. Nó so sánh giá trị target với giá trị ở giữa (arr[mid]) và dịch chuyển ranh giới trái hoặc phải của khoảng tìm kiếm dựa trên kết quả so sánh.

Nếu tìm thấy giá trị, nó trả về chỉ số của phần tử

Nếu không, nó trả về -1.

Nhược điểm của tìm kiếm nhị phân:

1. Chỉ áp dụng cho danh sách đã được sắp xếp: Thuật toán tìm kiếm nhị phân chỉ hoạt động hiệu quả trên danh sách đã được sắp xếp trước. Nếu danh sách chưa được sắp xếp, bạn phải sắp xếp danh sách trước khi áp dụng thuật toán này, và quá trình sắp xếp có độ phức tạp thời gian khá cao.
2. Không thích hợp cho dữ liệu thay đổi thường xuyên: Nếu bạn thường xuyên thêm hoặc xóa phần tử khỏi danh sách, thuật toán tìm kiếm nhị phân không phù hợp vì nó đòi hỏi danh sách phải được duyệt theo chỉ số cụ thể và đảm bảo được sắp xếp.
3. Không trả về tất cả các kết quả: Nếu có nhiều phần tử có giá trị giống nhau trong danh sách, thuật toán tìm kiếm nhị phân chỉ trả về một trong số chúng. Nếu bạn muốn tất cả các vị trí của giá trị cần tìm, bạn phải thực hiện thêm công việc để tìm kiếm tất cả các trùng lặp.
4. Không hiệu quả với danh sách liên kết: Tìm kiếm nhị phân hoạt động tốt với mảng, nhưng nó không hiệu quả với danh sách liên tục (linked list) do việc truy cập ngẫu nhiên vào các nút của danh sách liên tục cần phải thực hiện theo chỉ số.
5. Khả năng gây lãng phí bộ nhớ: Thuật toán tìm kiếm nhị phân thường thực hiện đệ quy hoặc sử dụng ngăn xếp (stack) để lưu trữ thông tin về khoảng tìm kiếm. Điều này có thể gây ra lãng phí bộ nhớ nếu danh sách quá lớn và độ sâu đệ quy lớn.

Các bài viết không xem thì tiếc:

• Thuật toán tìm kiếm tuyến tính (Linear Search)
• Làm việc với font trong Android
• Cách dùng AsyncTask trong Android
• Little Endian Unsinged trong Java
• Lưu ý khi porting C/C++ sang Java
• 7 lời khuyên của Sam Altman để thành công
• Copy mảng byte trong Java bằng Arrays.copyOfRange()
• Thiết kế website số 1 Việt Nam và thiết kế web top 1 Google
• Cách dùng Eventbus để truyền dữ liệu trong Android
• Tổng quan nhất về ứng dụng Android
• Trang web nổi tiếng nào được làm bằng PHP?
• Công ty SI là gì trong lĩnh vực công nghệ thông tin?
• Gửi dữ liệu đến BLESerial3 bằng Bluetooth LE Android
• Truyền dữ liệu giữa 2 fragment trong android
• Danh sách bluetooth profiles