Lập trình Java

Thuật toán Tìm kiếm Nhị phân (Binary Search) trong Java

Posted on by Đỗ Thành
18
Th3
View: 72

Tìm kiếm nhị phân là một thuật toán tìm kiếm hiệu quả được sử dụng để tìm một phần tử trong một mảng đã được sắp xếp. Thuật toán này hoạt động bằng cách liên tục chia đôi mảng và so sánh giá trị cần tìm với phần tử ở giữa. Dựa trên kết quả so sánh, thuật toán sẽ quyết định tiếp tục tìm kiếm ở nửa bên trái hoặc nửa bên phải của mảng.

Ý tưởng chính

  1. Mảng phải được sắp xếp trước khi áp dụng thuật toán.
  2. Chọn phần tử ở giữa mảng.
  3. So sánh phần tử ở giữa với giá trị cần tìm:
    • Nếu bằng nhau, trả về vị trí của phần tử.
    • Nếu giá trị cần tìm nhỏ hơn phần tử ở giữa, tiếp tục tìm kiếm ở nửa bên trái.
    • Nếu giá trị cần tìm lớn hơn phần tử ở giữa, tiếp tục tìm kiếm ở nửa bên phải.
  4. Lặp lại quá trình cho đến khi tìm thấy phần tử hoặc không còn phần tử nào để kiểm tra.

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

  • O(log n) : Do mỗi lần lặp giảm số lượng phần tử cần kiểm tra đi một nửa.

Cài đặt thuật toán Tìm kiếm Nhị phân trong Java

Dưới đây là hai cách cài đặt thuật toán tìm kiếm nhị phân trong Java:

  1. Sử dụng vòng lặp (Iterative).
  2. Sử dụng đệ quy (Recursive).

Cài đặt bằng vòng lặp (Iterative)

public class BinarySearchIterative {
    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; // Tính chỉ số giữa để tránh tràn số

            // So sánh phần tử ở giữa với giá trị cần tìm
            if (arr[mid] == target) {
                return mid; // Trả về vị trí nếu tìm thấy
            } else if (arr[mid] < target) {
                left = mid + 1; // Tiếp tục tìm kiếm ở nửa bên phải
            } else {
                right = mid - 1; // Tiếp tục tìm kiếm ở nửa bên trái
            }
        }

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

    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int target = 23;

        int result = binarySearch(arr, target);

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

Cài đặt bằng đệ quy (Recursive)

public class BinarySearchRecursive {
    public static int binarySearch(int[] arr, int left, int right, int target) {
        if (left > right) {
            return -1; // Điều kiện dừng: không tìm thấy phần tử
        }

        int mid = left + (right - left) / 2; // Tính chỉ số giữa

        // So sánh phần tử ở giữa với giá trị cần tìm
        if (arr[mid] == target) {
            return mid; // Trả về vị trí nếu tìm thấy
        } else if (arr[mid] < target) {
            return binarySearch(arr, mid + 1, right, target); // Tìm kiếm ở nửa bên phải
        } else {
            return binarySearch(arr, left, mid - 1, target); // Tìm kiếm ở nửa bên trái
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int target = 72;

        int result = binarySearch(arr, 0, arr.length - 1, target);

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

Giải thích mã nguồn:

  1. Vòng lặp (Iterative):
    • Biến left và right đại diện cho phạm vi tìm kiếm hiện tại.
    • Tính chỉ số giữa mid và so sánh giá trị tại arr[mid] với target.
    • Cập nhật left hoặc right để thu hẹp phạm vi tìm kiếm.
  2. Đệ quy (Recursive):
    • Hàm binarySearch gọi chính nó với phạm vi tìm kiếm mới (left, right) dựa trên kết quả so sánh.
    • Điều kiện dừng là khi left > right, tức là không còn phần tử nào để kiểm tra.

Kết quả chạy ví dụ:

Giả sử mảng đầu vào là {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} và giá trị cần tìm là 23.

  • Kết quả: Phần tử 23 được tìm thấy tại vị trí: 5.

Ưu điểm và nhược điểm của Tìm kiếm Nhị phân

Ưu điểm:

  • Hiệu quả cao với độ phức tạp O(log n).
  • Phù hợp cho các bài toán tìm kiếm trên mảng lớn.

Nhược điểm:

  • Yêu cầu mảng phải được sắp xếp trước khi thực hiện tìm kiếm.
  • Không phù hợp với cấu trúc dữ liệu không có thứ tự (ví dụ: danh sách liên kết).

Kết luận

Thuật toán tìm kiếm nhị phân là một phương pháp tìm kiếm mạnh mẽ và hiệu quả trong các trường hợp mảng đã được sắp xếp. Bạn có thể lựa chọn giữa cách cài đặt vòng lặp hoặc đệ quy tùy thuộc vào yêu cầu cụ thể của bài toán./.

Đỗ Thành