/codegym.vn/ - 137
Chương 7 - Thuật toán tìm kiếm
Thực hiện được các thao tác tìm kiếm dữ liệu một cách hiệu quả
1. Mục tiêu
● Trình bày được mục đích của các thuật toán tìm kiếm
● Trình bày được ý tưởng và các bước thực hiện của thuật toán tìm kiếm tuyến
tính
● Triển khai được thuật toán tìm kiếm tuyến tính trên mảng
● Trình bày được ý tưởng và các bước thực hiện của thuật toán tìm kiếm tuyến
tính
● Triển khai được thuật toán tìm kiếm nhị phân trên mảng
● Tính toán được độ phức tạp của thuật toán tuyến tính và tìm kiếm nhị phân
● Phân biệt được các tình huống nên sử dụng thuật toán tìm kiếm tuyến tính và
tìm kiếm nhị phân
2. Giới thiệu
Tìm kiếm là một trong những thao tác căn bản nhất khi làm việc với dữ liệu. Tìm kiếm
khách hàng, tìm kiếm sản phẩm hoặc tìm kiếm các thông tin khác nói chung đều là
những tính năng mà ta bắt gặp hằng ngày ở các phần mềm. Ở mức độ giải thuật cũng
vậy, các lập trình viên thường xuyên tiếp xúc với những tình huống mà ở đó cần đến
việc triển khai thuật toán tìm kiếm: tìm kiếm xem liệu dữ liệu có tồn tại hay không, tìm
kiếm vị trí của dữ liệu, tìm kiếm dữ liệu dựa trên một đặc điểm nhất định, v.v.
Ở trong chương này, chúng ta sẽ thảo luận về một số thuật toán tìm kiếm căn bản
nhất. Dựa trên các thuật toán này, về sau chúng ta có thể triển khai thêm các thuật
toán tìm kiếm phù hợp để đáp ứng được yêu cầu của tình huống cụ thể. Hai thuật
toán tìm kiếm mà chúng ta sẽ đề cập đến đó là tìm kiếm tuyến tính và tìm kiếm nhị
phân.
Hoàn thành chương này, chúng ta có thể xây dựng được các tính năng cho các ứng
dụng phần mềm mà ở đó cần triển khai thao tác tìm kiếm dựa trên các tiêu chí khác
nhau.
3. Tìm kiếm tuyến tính
Tìm kiếm tuyến tính (linear search) là thuật toán mà ở đó chúng ta duyệt dữ liệu lần
lượt từ đầu đến cuối để tìm ra phần tử phù hợp với yêu cầu đặt ra. Thuật toán này
thuộc nhóm “vét cạn”: chúng ta sẽ cố gắng duyệt và kiểm tra lần lượt tất cả các trường
hợp.
