Bài giảng Cấu trúc dữ liệu và giải thuật: Giải thuật tìm kiếm tuyến tính và nhị phân gồm các nội dung chính sau giới thiệu bài toán tìm kiếm; tìm kiếm tuyến tính; tìm kiếm nhị phân. Mời các bạn cùng tham khảo! | GIẢI THUẬT TÌM KIẾM TUYẾN TÍNH amp NHỊ PHÂN Giải thuật algorithms đó là dãy các câu lệnh statements chặt chẽ và rõ ràng xác định trình tự các thao tác trên một số đối tượng nào đó sao cho sau một số hữu hạn bước thực hiện ta đạt được kết quả mong muốn. Thuật toán là một dãy hữu hạn các bước mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện để giải quyết một vấn đề. Niklous Wirth cha đẻ của ngôn ngữ lập trình Pascal và kỹ thuật lập trình cấu trúc đã đúc kết ý nghĩa của dữ liệu và mối quan hệ hữu cơ của nó với giải thuật bằng mệnh đề nổi tiếng Chương trình Thuật toán Cấu trúc dữ liệu 4 KHOA CÔNG NGHỆ THÔNG TIN Bài toán được mô tả như sau Tập dữ liệu được lưu trữ là dãy a1 a2 . an. Giả sử chọn cấu trúc dữ liệu mảng để lưu trữ dãy số này trong bộ nhớ chính có khai báo int a n Khóa cần tìm là x int x Tìm kiếm Tìm kiếm tuyến tính Tìm kiếm nhị phân Tập dữ liệu Tập dữ liệu đã bất kỳ được sắp xếp 5 KHOA CÔNG NGHỆ THÔNG TIN Ý tưởng duyệt tuần tự từ phần tử đầu tiên lần lượt so sánh khóa tìm kiếm với khoá tương ứng của các phần tử trong danh sách. Cho đến khi gặp phần tử cần tìm duyệt hết danh sách. Các bước tiến hành như sau i 0 S i Ý tưởng Lần lượt so sánh x với phần tử thứ nhất thứ hai . của mảng a cho đến khi gặp được phần tử cần tìm hoặc hết mảng 7 KHOA CÔNG NGHỆ THÔNG TIN Ví dụ Cho dãy số a giá trị tìm x 6 12 2 5 8 1 6 4 x 6 Tìm thấy 12 2 5 8 1 6 4 i 0 i 1 i 2 i 3 i 4 i 5 i 6 x 10 Không tìm thấy 12 2 5 8 1 6 4 i 0 i 1 i 2 i 3 i 4 i 5 i 6 8 KHOA CÔNG NGHỆ THÔNG TIN Giải thuật Bước 1 i 0 bắt đầu từ phần tử đầu tiên của dãy Bước 2 So sánh a i với x có 2 khả năng a i x Tìm thấy. Dừng kết thúc. a i x Chuyển sang Bước 3. Bước 3 i i 1 xét phần tử kế tiếp trong mảng Nếu i gt n Hết mảng không tìm thấy. Dừng Ngược lại quay lui Bước 2. 9 KHOA CÔNG NGHỆ THÔNG TIN Thuật toán tìm kiếm tuyến tính Trả về vị trí xuất hiện đầu tiên của x trong mảng a Trả về -1 nếu x không có trong mảng a int Search int a int n int key int i 0 while i Thuật toán tìm kiếm tuyến tính cải
