Tags:

Tìm phần tử X trong mảng tăng dần, không biết được số lượng phần tử của mảng

Viết chương trình tìm phần tử X trong mảng tăng dần, không cho biết số lượng phần tử. 

 Như hình trên, thì N chúng ta sẽ không được biết, chúng ta chỉ biết được sức chứa của mảng là size.

Ở đây, mình sẽ dùng kiểu Integer, thay vì sử dụng kiểu dữ liệu nguyên thuỷ int. Lý do là vì mảng int khi khởi tạo sẽ tự động gán các giá trị của mảng bằng 0, việc này sẽ ảnh hưởng đến kết quả tìm kiếm .

Cách 1: Linear search

Để sử dụng linear search, chúng ta cũng cần custom lại một tý để tránh duyệt hết các phần tử chưa được khởi tạo.

Sử dụng linear search sẽ tốn θ(n).

public class Main {

    public static void main(String[] args) {
        Integer[] arr = new Integer[1000];
        int n = 50; // We don't know number of element in array => hide
        // init array sorted ascending
        for (int i = 0; i < n; i++) {
            arr[i] = i;
        }
        int pos = linearSearch(arr, 25);
        if (pos == -1) {
            System.out.println("Not found");
        } else {
            System.out.println("Element found at: " + pos);
        }
    }

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

Output: Element found at  25

Cách 2: Binary search

Binary search hoạt động tìm kiếm trong một khoảng [a, b] được sắp xếp, Khi tìm kiếm trong mảng, thì a là vị trí phần tử đầu tiên của mảng, b là vị trí phần tử cuối cùng.

Nhưng, chúng ta không biết được b, mà chúng ta chỉ biết sức chứa của mảng là size.  :-P. Mình sẽ áp dụng binary search cho khoảng [0, size – 1] vì mình chỉ biết được size thôi =)). Những phần tử chưa được khởi tạo mình sẽ xem nó như là một số rất lớn, rồi áp dụng binary search.

Sử dụng binary search sẽ tốn θ(Log(n)). 

1: Khởi tạo 
    + L = vị trí đầu tiên của khoảng tìm kiếm.
    + R: phần tử cuối cùng của khoảng tìm kiếm.
B2: Trong khi L <= R: middle = L + (R - L) / 2
    + Nếu arr[middle] > X || arr[middle] == null: R = middle - 1
    + Nếu arr[middle == X: return middle
    + Nếu arr[middle] < X: L = middle + 1
B3: return -1 nếu không tìm thấy
public class Main {

    public static void main(String[] args) {
        Integer[] arr = new Integer[1000];
        int n = 50; // We don't know number of element in array => hide
        // init array sorted ascending
        for (int i = 0; i < n; i++) {
            arr[i] = i;
        }
        int pos = binarySearchCustom(arr, 25);
        if (pos == -1) {
            System.out.println("Not found");
        } else {
            System.out.println("Element found at: " + pos);
        }
    }
    public static int binarySearchCustom(Integer[] arr, int value) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (arr[m] == null || arr[m] > value) {
                r = m - 1;
            } else if (arr[m] == value) {
                return m;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }
}

Output: Element found at  25

Link source-code: source

Nguồn tham khảo: geeksforgeeks

0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x