Bài giảng Thuật toán ứng dụng: Tìm kiếm và Sắp xếp cung cấp cho người học những kiến thức như: Tìm kiếm tuyến tính, nhị phân; Sắp xếp; Các cấu trúc dữ liệu trừu tượng. Mời các bạn cùng tham khảo! | THUẬT TOÁN ỨNG DỤNG Tìm kiếm và Sắp xếp Nội dung 1. Tìm kiếm 1. Tuyến tính 2. Nhị phân 2. Sắp xếp 1. Nổi bọt Chèn Chọn 2. Trộn Nhanh Vun đống 3. Các cấu trúc dữ liệu trừu tượng 1. Stack 2. Queue 3. Heap 4. Set 5. Map TRƯƠNG XUÂN NAM 2 Phần 1 Tìm kiếm TRƯƠNG XUÂN NAM 3 Tìm kiếm Bài toán cơ bản nhất của máy tính Tìm thành phần trên trang màn hình Tìm tên trong danh bạ Tìm kiếm web Câu trả lời Có dữ liệu cần tìm hay không Vị trí của dữ liệu cần tìm Tùy vào dữ liệu Dữ liệu lộn xộn không có đặc trưng gì cụ thể Dữ liệu được sắp xếp Dữ liệu được tổ chức TRƯƠNG XUÂN NAM 4 Tìm kiếm tuyến tính linear search Giải thuật tìm kiếm cơ bản nhất Dữ liệu lộn xộn không có tính chất gì đặc biệt Duyệt mọi phần tử từ đầu cho đến khi tìm được dữ liệu mong muốn hoặc hết dữ liệu Có lẽ là cách giải duy nhất trong trường hợp bài toán không có ràng buộc về dữ liệu TRƯƠNG XUÂN NAM 5 Tìm kiếm nhị phân binary search Dữ liệu đã được sắp xếp tăng dần Chia đôi khoảng tìm kiếm cho đến khi đủ nhỏ tìm kiếm nhị phân cài đặt kiểu đệ quy int binary_search int arr int l int r int x if r lt l return -1 int mid l r - l 2 tìm thấy ở giữa if arr mid x return mid tìm ở nửa trước if arr mid gt x return binary_search arr l mid - 1 x tìm ở nửa sau return binary_search arr mid 1 r x TRƯƠNG XUÂN NAM 6 Tìm kiếm nhị phân binary search Cài đặt kiểu vòng lặp ổn hơn kiểu đệ quy ở chỗ nào Cài đặt dưới đây có thể cải tiến ở điểm nào tìm kiếm nhị phân cài đặt bằng vòng lặp int binary_search2 int arr int l int r int x while l Tìm kiếm nội suy interpolation search Tìm kiếm khi dữ liệu cực lớn đã được sắp xếp Cải tiến từ tìm kiếm nhị phân vẫn chia đôi nhưng cân nhắc theo tương quan của dữ liệu Thích hợp với dữ liệu cực lớn và cân bằng tìm kiếm nội suy nhị phân thông minh hơn int interpolation_search int a int l int r int x while l Cài đặt tìm kiếm ở thư viện STL C Thư viện Tìm tuyến tính find tìm giá trị trong đoạn Tìm nhị phân binary_search kiểm tra xem có phần tử trong đoạn tăng dần hay không lower_bound trả về vị trí của
