Thuật toán tìm kiếm trong Java

Thuật toán tìm kiếm tuyến tính trong java

Thuật toán tìm kiếm tuyến tính (linear search) trong Java được thực hiện bằng cách duyệt từng phần tử trong mảng và so sánh với giá trị cần tìm. Nếu tìm thấy phần tử có giá trị bằng với giá trị cần tìm, thuật toán sẽ trả về chỉ số của phần tử đó trong mảng. Nếu không tìm thấy, thuật toán sẽ trả về -1. Dưới đây là code của thuật toán tìm kiếm tuyến tính trong Java:

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

Trong đó, arr là mảng cần tìm kiếm, x là giá trị cần tìm. Hàm sẽ trả về chỉ số đầu tiên mà giá trị x xuất hiện trong mảng arr, hoặc trả về -1 nếu không tìm thấy x trong mảng.

Để sử dụng thuật toán tìm kiếm tuyến tính này, bạn có thể gọi hàm linearSearch(arr, x) và truyền vào mảng cần tìm kiếm và giá trị cần tìm.

Thuật toán tìm kiếm nhị phân trong Java

Thuật toán tìm kiếm nhị phân (binary search) trong Java là một thuật toán hiệu quả để 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 tìm kiếm trung điểm của mảng, so sánh giá trị tại vị trí đó với giá trị cần tìm, và tiếp tục tìm kiếm trong nửa mảng phù hợp.

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

public static int binarySearch(int[] arr, int x) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x) {
            return mid;
        } else if (arr[mid] < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

Trong đó, arr là mảng đã được sắp xếp cần tìm kiếm, x là giá trị cần tìm. Hàm sẽ trả về chỉ số của giá trị x trong mảng arr nếu tìm thấy, hoặc trả về -1 nếu không tìm thấy.

Cách sử dụng thuật toán tìm kiếm nhị phân này là gọi hàm binarySearch(arr, x) và truyền vào mảng đã được sắp xếp và giá trị cần tìm.

Dưới đây là một ví dụ về cách sử dụng thuật toán tìm kiếm nhị phân trong Java để tìm kiếm một số nguyên trong một mảng đã được sắp xếp:

public class BinarySearchExample {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        int x = 7;
        int index = binarySearch(arr, x);
        if (index == -1) {
            System.out.println("Không tìm thấy giá trị " + x + " trong mảng.");
        } else {
            System.out.println("Tìm thấy giá trị " + x + " tại vị trí " + index + " trong mảng.");
        }
    }

    public static int binarySearch(int[] arr, int x) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == x) {
                return mid;
            } else if (arr[mid] < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

Trong ví dụ này, chúng ta có một mảng đã được sắp xếp {1, 3, 5, 7, 9, 11} và muốn tìm kiếm giá trị 7. Chúng ta gọi hàm binarySearch(arr, x) với arr là mảng đã được sắp xếp và x là giá trị cần tìm.

Kết quả trả về từ hàm là vị trí của giá trị 7 trong mảng. Nếu không tìm thấy giá trị, hàm sẽ trả về giá trị -1. Trong ví dụ này, giá trị 7 được tìm thấy tại vị trí thứ 3 trong mảng đã cho.