Tìm kiếm mảng tuyến tính
Rất thường xuyên, bạn cần tìm một giá trị đã cho trong một mảng hoặc báo cáo rằng nó không có ở đó. Để làm điều này, bạn cần xem qua tất cả các phần tử của mảng từ phần tử đầu tiên đến phần tử cuối cùng. Ngay khi tìm thấy một phần tử bằng với giá trị X đã cho, quá trình tìm kiếm sẽ kết thúc và kết quả sẽ được hiển thị. Thuật toán như vậy được gọi là tuyến tính.
Một thuật toán tuyến tính được sử dụng để tìm phần tử tối đa (tối thiểu) của một mảng. Đây cũng là một thuật toán tìm kiếm. Nhưng ở đây chúng ta buộc phải đi đến cuối mảng, bởi vì cần phải so sánh tất cả các phần tử với giá trị tối đa (tối thiểu) hiện tại và nếu phần tử hiện tại lớn hơn (nhỏ hơn) giá trị tối đa (tối thiểu), hãy thay thế giá trị tối đa (tối thiểu).
|
Một cách tiếp cận khác để giải quyết vấn đề này là có thể. Bạn có thể sử dụng lối thoát sớm khỏi vòng lặp nếu tìm thấy giá trị cần thiết.
Trong C++, câu lệnh break được sử dụng để thoát ra khỏi vòng lặp;
|
Tìm kiếm nhị phân
Tìm kiếm nhị phân (hoặc nhị phân) là thuật toán tìm kiếm hiệu quả và nhanh hơn tìm kiếm tuyến tính. Ví dụ: đối với một mảng gồm 1024 phần tử, tìm kiếm tuyến tính trong trường hợp xấu nhất (khi phần tử mong muốn không có trong mảng) sẽ xử lý tất cả 1024 phần tử, nhưng nó đủ để xử lý 10 phần tử bằng tìm kiếm nhị phân. Kết quả này đạt được là do sau bước đầu tiên của vòng lặp, khu vực tìm kiếm thu hẹp xuống còn 512 phần tử, sau bước thứ hai – lên đến 256, v.v.
Nhược điểm của thuật toán như vậy là yêu cầu sắp xếp thứ tự dữ liệu, cũng như khả năng truy cập bất kỳ phần tử dữ liệu nào trong một khoảng thời gian không đổi (không phụ thuộc vào lượng dữ liệu). Do đó, thuật toán không thể hoạt động trên mảng không có thứ tự.
Thuật toán
- Chọn phần tử ở giữa
A[c] và so sánh với X.
- Nếu
X = A[c] thì tìm thấy (dừng).
- Nếu
X < A[c], tìm kiếm thêm trong nửa đầu.
- Nếu
X > A[c], hãy xem thêm nửa sau.
Triển khai
L = 0; R=N; // đoạn đầu
trong khi ( L < R - 1)
{
c = (L + R)/2; // tìm thấy giữa
if ( X < A[c] ) // nén đoạn
R=c;
khác
L = c;
}
nếu ( A[L] == X)
cout << "A" << Đ<< "]=" << x;
khác
cout << "Không tìm thấy";
ở đâu:
A - mảng nguồn,
N - kích thước mảng,
X - số đã tìm kiếm,
Có thể triển khai các cách khác.
Ví dụ: sử dụng lối thoát sớm khỏi vòng lặp
L = 0; R = N - 1;
trong khi (R >= L)
{
c = (L + R)/2;
nếu ( X == A[c] )
{
nX = c;
phá vỡ;
}
if (X < A[c]) R = giữa - 1;
if (X > A[c]) L = giữa + 1;
}
nếu ( nX < 0)
cout << "Không tìm thấy";
khác
cout << "A" << nX<< "]=" << X;
|
So sánh thuật toán tìm kiếm tuyến tính và thuật toán tìm kiếm nhị phân theo số lần so sánh
Ví dụ
<đầu>
| # |
Tìm kiếm theo dòng |
Tìm kiếm nhị phân |
| 2 |
2 |
2 |
| 16 |
16 |
5 |
| 1024 |
1024 |
11 |
| 1048576 |
1048576 |
21 |
Ưu điểmcủa sắp xếp nhị phân là nhanh hơn.
Nhược điểm- bắt buộc phải có một mảng được sắp xếp trước.
|