Chương trình Java tìm kiếm tuyến tính đệ quy trong mảng

Giới thiệu

Trong bài viết này, chúng ta sẽ tìm hiểu cách tìm kiếm tuyến tính đệ quy (recursive linear search) một phần tử trong mảng. Tìm kiếm tuyến tính là thuật toán tìm kiếm đơn giản, kiểm tra lần lượt từng phần tử theo thứ tự.

Minh họa

Đầu vào:

Input array: 14 20 35 47 50 65 72 81 90 99 Key element: 72

Đầu ra mong muốn:

The element 72 is present at position: 6

Thuật toán

1. Bắt đầu
2. Khai báo: mảng input_array, số nguyên key_element, index
3. Khởi tạo giá trị
4. Duyệt mảng, xác định phần tử cần tìm, gọi hàm đệ quy với các tham số
5. Điều kiện if: nếu thất bại trả về -1, thành công trả về vị trí phần tử
6. Hiển thị kết quả
7. Kết thúc

Ví dụ 1: Tìm kiếm trên mảng số nguyên

public class LinearSearch {
    static int recSearch(int input_array[], int l, int r, int key_element) {
        if (r < l)
            return -1;
        if (input_array[l] == key_element)
            return l;
        if (input_array[r] == key_element)
            return r;
        return recSearch(input_array, l+1, r-1, key_element);
    }
    
    public static void main(String[] args) {
        int input_array[] = {14, 20, 35, 47, 50, 65, 72, 81, 90, 99};
        System.out.println("The elements of the array is defined as ");
        for (int i : input_array) {
            System.out.print(i + " ");
        }
        
        int key_element = 72;
        System.out.println("\n\nThe elements to be searched in the array is: " + key_element);
        
        int index = recSearch(input_array, 0, input_array.length-1, key_element);
        
        if (index != -1)
            System.out.println("\nThe element " + key_element + " is present at position: " + index);
        else
            System.out.println("Element " + key_element + " is not present: ");
    }
}

Đầu ra

The elements of the array is defined as 14 20 35 47 50 65 72 81 90 99
The elements to be searched in the array is: 72
The element 72 is present at position: 6

Ví dụ 2: Tìm kiếm trên mảng chuỗi

public class Demo {
    static int recSearch(String input_array[], int l, int r, String key_element) {
        if (r < l)
            return -1;
        if (input_array[l].equals(key_element))
            return l;
        if (input_array[r].equals(key_element))
            return r;
        return recSearch(input_array, l+1, r-1, key_element);
    }
    
    public static void main(String[] args) {
        String input_array[] = { "Scala", "Java", "Python", "Mysql" };
        System.out.println("The elements of the array is defined as ");
        for (String i : input_array) {
            System.out.print(i + " ");
        }
        
        String key_element = "Java";
        System.out.println("\n\nThe elements to be searched in the array is: " + key_element);
        
        int index = recSearch(input_array, 0, input_array.length-1, key_element);
        
        if (index != -1)
            System.out.println("\nThe element " + key_element + " is present at position: " + index);
        else
            System.out.println("Element " + key_element + " is not present: ");
    }
}

Đầu ra

The elements of the array is defined as Scala Java Python Mysql
The elements to be searched in the array is: Java
The element Java is present at position: 1