Giải Thuật Tìm Kiếm: Tuyến Tính và Nhị Phân (Java)

Chào mừng bạn đến với bài viết thứ 10 trong series về cấu trúc dữ liệu và giải thuật. Hôm nay, chúng ta sẽ khám phá hai giải thuật tìm kiếm cơ bản. Đó là tìm kiếm tuyến tính và tìm kiếm nhị phân. Chúng ta sẽ tìm hiểu cách chúng hoạt động. Đồng thời, chúng ta cũng sẽ xem xét khi nào nên sử dụng chúng. Ví dụ minh họa sẽ được viết bằng Java.

Tìm Kiếm Tuyến Tính (Linear Search)

Tìm kiếm tuyến tính là một thuật toán đơn giản. Nó duyệt qua từng phần tử của mảng. Nó so sánh mỗi phần tử với giá trị cần tìm. Nếu tìm thấy giá trị, thuật toán trả về vị trí của nó. Nếu duyệt hết mảng mà không tìm thấy, thuật toán trả về giá trị đặc biệt (ví dụ: -1).

Dưới đây là một ví dụ triển khai tìm kiếm tuyến tính trong Java:

public class LinearSearch {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 5, 6};
        int target = 9;
        int index = linearSearch(arr, target);
        if (index != -1) {
            System.out.println("Phần tử được tìm thấy tại vị trí: " + index);
        } else {
            System.out.println("Không tìm thấy phần tử.");
        }
    }
}

Khi Nào Nên Sử Dụng Tìm Kiếm Tuyến Tính?

Tìm kiếm tuyến tính phù hợp trong các trường hợp sau:

• Mảng có kích thước nhỏ.
• Dữ liệu không được sắp xếp.
• Bạn chỉ cần thực hiện tìm kiếm một vài lần.

Mặc dù đơn giản, tìm kiếm tuyến tính có độ phức tạp thời gian là O(n). Điều này có nghĩa là thời gian thực hiện tăng tuyến tính với kích thước của mảng. Đối với các mảng lớn, nó có thể trở nên chậm chạp.

Tìm Kiếm Nhị Phân (Binary Search)

Tìm kiếm nhị phân là một thuật toán hiệu quả hơn. Nó được sử dụng để tìm kiế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 chia đôi mảng. Nó so sánh phần tử ở giữa với giá trị cần tìm. Nếu chúng bằng nhau, thuật toán trả về vị trí. Nếu giá trị cần tìm nhỏ hơn, thuật toán tiếp tục tìm kiếm ở nửa bên trái. Nếu lớn hơn, thuật toán tìm kiếm ở nửa bên phải. Quá trình này lặp lại cho đến khi tìm thấy phần tử hoặc không gian tìm kiếm trở nên trống rỗng.

Nguyên Lý Hoạt Động

1. Xác định điểm giữa của mảng.

2. So sánh giá trị tại điểm giữa với giá trị cần tìm.

3. Nếu bằng nhau, trả về vị trí.

4. Nếu giá trị cần tìm nhỏ hơn, tìm kiếm ở nửa bên trái.

5. Nếu giá trị cần tìm lớn hơn, tìm kiếm ở nửa bên phải.

6. Lặp lại các bước trên cho đến khi tìm thấy phần tử hoặc không gian tìm kiếm trống rỗng.

Yêu Cầu Dữ Liệu Phải Được Sắp Xếp

Điểm quan trọng nhất của tìm kiếm nhị phân là dữ liệu phải được sắp xếp. Nếu dữ liệu không được sắp xếp, kết quả tìm kiếm sẽ không chính xác. Việc sắp xếp dữ liệu trước khi tìm kiếm bằng thuật toán nhị phân có thể tốn thời gian. Tuy nhiên, đối với các mảng lớn và tìm kiếm nhiều lần, việc này vẫn có thể hiệu quả hơn so với tìm kiếm tuyến tính.

Dưới đây là một ví dụ triển khai tìm kiếm nhị phân trong Java:

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2; // Ngăn chặn tràn số

            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 5, 5, 6, 9};
        int target = 5;
        int index = binarySearch(arr, target);
        if (index != -1) {
            System.out.println("Phần tử được tìm thấy tại vị trí: " + index);
        } else {
            System.out.println("Không tìm thấy phần tử.");
        }
    }
}

Tìm kiếm nhị phân có độ phức tạp thời gian là O(log n). Điều này có nghĩa là thời gian thực hiện tăng theo logarit của kích thước mảng. Nó hiệu quả hơn nhiều so với tìm kiếm tuyến tính cho các mảng lớn.

So Sánh Tìm Kiếm Tuyến Tính và Tìm Kiếm Nhị Phân

Kết luận

Trong bài viết này, chúng ta đã tìm hiểu về hai thuật toán tìm kiếm cơ bản: tìm kiếm tuyến tính và tìm kiếm nhị phân. Tìm kiếm tuyến tính đơn giản nhưng kém hiệu quả với mảng lớn. Tìm kiếm nhị phân hiệu quả hơn nhiều nhưng yêu cầu dữ liệu phải được sắp xếp. Hãy lựa chọn thuật toán phù hợp dựa trên yêu cầu cụ thể của bạn. Tiếp tục khám phá các giải thuật và cấu trúc dữ liệu khác để nâng cao kỹ năng lập trình của bạn!