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

Thuật toán Tìm kiếm Nhị phân là một phương pháp hiệu quả trong lập trình Java, được sử dụng để tìm kiếm một giá trị cụ thể trong một mảng đã sắp xếp. Phương pháp này hoạt động bằng cách liên tục chia mảng thành hai phần và so sánh giá trị tìm kiếm với giá trị ở vị trí giữa.

Cách hoạt động của Thuật toán Tìm kiếm Nhị phân

Thuật toán Tìm kiếm Nhị phân bắt đầu bằng cách so sánh giá trị tìm kiếm với phần tử ở giữa mảng. Nếu giá trị tìm kiếm bằng phần tử giữa, thuật toán trả về vị trí của phần tử. Nếu giá trị tìm kiếm nhỏ hơn phần tử giữa, thuật toán tiếp tục tìm kiếm trong nửa phần tử bên trái của mảng. Nếu giá trị tìm kiếm lớn hơn, thuật toán tiếp tục tìm kiếm trong nửa phần tử bên phải của mảng. Quá trình này lặp lại cho đến khi giá trị tìm kiếm được tìm thấy hoặc không còn phần tử nào để tìm kiếm.

Ưu nhược điểm của Thuật toán Tìm kiếm Nhị phân

Ưu điểm:

• Hiệu suất cao: Thuật toán này loại bỏ một nửa các phần tử trong mỗi bước, giúp tối ưu hóa tìm kiếm trên các mảng lớn.
• Độ phức tạp thời gian thấp: Thời gian tìm kiếm của thuật toán này có độ phức tạp O(log n), làm cho nó hiệu quả với các tập dữ liệu lớn.

Nhược điểm:

• Mảng phải được sắp xếp: Thuật toán chỉ hoạt động với các mảng đã được sắp xếp.

Ví dụ và Giải thích

Hãy xem xét một ví dụ về việc sử dụng thuật toán Tìm kiếm Nhị phân để tìm một số nguyên cụ thể trong một mảng số nguyên đã sắp xếp trong Java.

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

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

            if (array[mid] == target) {
                return mid; // Trả về vị trí nếu tìm thấy
            } else if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1; // Trả về -1 nếu không tìm thấy
    }

    public static void main(String[] args) {
        int[] numbers = { 1, 3, 5, 7, 9, 11, 13, 15 };
        int target = 9;

        int position = binarySearch(numbers, target);

        if (position != -1) {
            System.out.println("Element " + target + " found at position " + position);
        } else {
            System.out.println("Element " + target + " not found in the array");
        }
    }
}

Trong ví dụ này, chúng ta sử dụng thuật toán Tìm kiếm Nhị phân để tìm số 9 trong mảng số nguyên đã sắp xếp. Thuật toán lặp qua mảng và so sánh giá trị tìm kiếm với giá trị ở vị trí giữa. Trong trường hợp này, số 9 được tìm thấy tại vị trí thứ 4 (0-based index) của mảng.

Mặc dù ví dụ này thể hiện cách thuật toán Tìm kiếm Nhị phân có thể tìm kiếm một