Linear Search - Tìm kiếm tuần tự

Chào các bạn!

Tiếp theo chuỗi series về các thuật toán sắp xếp và tìm kiếm căn bản, thì ở bài viết này mình sẽ trình bày các bạn phần thuật toán tìm kiếm tuần tự.

Thuật toán khá đơn giản, nên chắc cũng không cần vòng vo nhiều nữa, chúng ta vào chi tiết ngay nhé.

Đặt vấn đề

Cho dãy số có kích thước N phần tử và số X. Hãy xác định vị trí đầu tiên mà X xuất hiện trong dãy số.

Ý tưởng thuật toán

Lần lượt duyệt qua từng phần tử và kiểm tra, nếu gặp X thì thoát và trả về giá trị vị trí.

Và dưới đây là code mà mình đã chuẩn bị:

int linearSearch(int *arr, int X) { for (int i=0; i<sz; i++){ if (X == arr[i]) return i; } return -1;
}

Full code bạn có thể xem ở đây: https://ideone.com/Hc5Fb8

Đánh giá độ phức tạp

Dễ thấy rằng, độ phức tạp của giải thuật trên là $O(N)$, nhưng tùy theo vị trí của $X$ ở đâu mà xác định thời gian nhanh hay chậm.

Và nếu bạn nhấn vào link full code ở phía trên, bạn sẽ tìm thấy dòng

Total time for search: 3(s)

Đoạn code trên mình đã tạo ra dãy số 10tr số tự nhiên đầu tiên bỏ vào dãy arr. Rồi sau đó sinh ngẫu nhiên số X nằm trong dãy số, rồi tìm kiếm trong 1000 lần.

Thì tổng thời gian tìm kiếm là tầm 3s.

Kết luận

Trên đây, mình đã trình bày các bạn về thuật toán Linear Search. Bài tiếp theo chúng ta sẽ cùng tìm hiểu về thuật toán tìm kiếm nhị phân nhé. Nó sẽ mạnh mẽ hơn thuật toán này gấp nhiều lần.

Nếu bạn có bất cứ ý kiến nào đóng góp, xin hãy gửi comment, mình sẽ trả lời và khắc phục cho những lần sau.