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)

,

  1. Để lại bình luận

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: