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 :

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:

function minMax(A, left, right, Min, Max){
if (left == right)
Min = Max = A[left];
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)