Tìm kiếm trên mảng

Tìm kiếm trên mảng


1. Thuật toán tìm kiếm nhị phân
o Bài toán
Cho một mảng các số được sắp xếp tăng dần (giảm dần), cho một giá trị x, xác định xem x có thuộc mảng đó hay không
o Ý tưởng
Giả sử mảng sắp xếp tăng dần A, ta chia đôi mảng, so sánh x với phần tử ở giữa A[mid], nếu:
- x == A[mid] : return true
- x > A[mid]: tiếp tục tìm x trong nửa mảng bên phải
- x < A[mid]: tiếp tục tìm x trong nửa mảng bên trái
o Mô tả thuật toán
- Input:
mảng A[1..n]
giá trí x
- Output:
 x thuộc A: true
 else false
- Method :

Code:

function binarySearch(A, x, first, last){
        if (first > last)
                return false;
        else{
                mid = (first + last) / 2;
                if (x == A[mid])
                        return true;
                else if (x < A[mid])
                        return binarySearch (A, x, first, mid - 1);
                else
                        return binarySearch (A, x, mid + 1, last);
        }
}

o Độ phức tạp tính toán: O(lgn)

2. Thuật toán tìm Min Max
o Bài toán
Tìm giá trí Min và Max trong đoạn [left, right] của mảng A[1,n]
o Ý tưởng
Chia mảng đoạn [left, right] thành 2 phần, tìm Min và Max trong 2 phần đó sau đó so sánh 2 kết quả này với nhau. Tiếp tục việc chia 2 cho đến khi đoạn chia chỉ còn 1 phần tử thì Min = Max và bằng phần tử đó
o Mô tả thuật toán
- Input:
Mảng A[1..n]
Left và Right
- Output: Min và Max của đoạn [Left, Right]
- Method:

Code:

function minMax(A, left, right, Min, Max){
        if (left == right)
                Min = Max = A;
        else{
                minMax(A, left, (right + left) / 2, Min1, Max1);
                minMax(A, (right + left) / 2 + 1, right, Min2, Max2);
                if (Min1 > Min2)
                        Min = Min2;
                else
                        Min = Min1;
                if(Max1 > Max2)
                        Max = Max1;
                else
                        Max = Max2;
        }
}

o Độ phức tạp tính toán: O(n)