Binary Search

Binary search là thuật toán tìm kiếm dựa trên mảng đã được sắp xếp. Một mảng được sắp xếp tăng dần thì phần tử ở giữa luôn thoả lớn hơn tức cả các phần tử bên trái, và bé hơn tất cả các phần tử bên phải. Dựa vào tính chất này, binary search hoạt động như sau:

B1: 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: return middle
    + Nếu arr[middle] < X: L = middle + 1
    + Nếu arr[middle] > X: R = middle - 1
B3: return -1 nếu không tìm thấy

Minh hoạ

Implementation

public static <T extends Comparable<T>> int search(T[] arr, T value) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (arr[m].equals(value)) {
                return m;
            }
            if (arr[m].compareTo(value) < 0) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return -1;
    }

Độ phức tạp

Với mỗi lần lặp khoảng tìm kiếm đều giảm đi một nữa, vậy độ phức tạp trung bình của Binary search là O(Log(n))

Link source code: BinarySearch