Bài giảng Cấu trúc dữ liệu và Giải thuật - Chương 2.1: Giải thuật tìm kiếm - Trần Minh Thái

Chương 2.1. Giải thuật tìm kiếmTrần Minh TháiEmail: minhthai@huflit.edu.vnWebsite: www.minhthai.edu.vn 1Mục tiêuXác định được vai trò của tìm kiếm và sắp xếp trong hệ thống thông tinNắm vững và minh họa được giải thuật tìm kiếm tuyến tính và tìm kiếm nhị phân trên mảng một chiềuCài đặt được giải thuật tìm kiếm bằng ngôn ngữ C#2Nhu cầu tìm kiếm và sắp xếpTìm kiếm: Có trong hầu hết trong các hệ thống thông tinMuốn tìm kiếm nhanh và hiệu quả  dữ liệu có thứ tự  sắp xếp3Vấn đề tìm kiếmDựa vào một phần thông tin được gọi là khoá (key)  tìm một mẫu tin (record) chứa các thông tin khác liên quan với khoá nàyCó thể có nhiều mẫu tin hoặc không có mẫu tin nào chứa khoá cần tìm4Đánh giá giải thuật tìm kiếmTìm kiếm thường là tác vụ tốn nhiều thời gian trong một chương trìnhTổ chức cấu trúc dữ liệu và giải thuật cho việc tìm kiếm ảnh hưởng lớn đến hiệu suất hoạt động của chương trìnhThông số đo chủ yếu là số lần so sánh khoá cần tìm với các mẫu tin khác5Phân loạiTìm kiếm nội và tìm kiếm ngoạiDữ liệu lưu trên thiết bị lưu trữ ngoài như đĩa hay băng từ: tìm kiếm ngoạiDữ liệu được lưu trữ trên bộ nhớ chính: tìm kiếm nội6Các giải thuật tìm kiếm trên dãyCó 2 giải thuật thường được áp dụng: Tìm tuần tự và tìm nhị phânĐặc tả:Tập dữ liệu được lưu trữ là dãy số a1, a2, ... ,aN. Khai báo: int []a = new int[N];Khóa cần tìm: int x;7a1a2a3a4a5an-1aNTìm kiếm tuần tự (Linear Search)Ý 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ảng8Tìm kiếm tuần tựMinh họa tìm x =10Minh họa tìm x =259Chưa hết mảng751241103213915312345678910751241103213915312345678910101025Chưa hết mảngĐã tìm thấy tại vị trí 5Đã hết mảngGiải thuật Bước 1:   i = 1;         // 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 a[i] != x :  Sang Bước 3. Bước 3:  i = i+1;      // xét tiếp phần tử kế trong mảng  Nếu i >N: Hết mảng, không tìm thấy. Dừng Ngược lại: Lặp lại Bước 2. 10Nguyên tắc cài đặt hàm tìm kiếmNếu có xuất hiện phần tử có giá trị x thì trả về vị trí tìm đượcNgược lại thì trả về -111Cài đặt int LinearSearch(int []a, int N, int x){ int i=0; while ((i r: Kết thúc: Không tìm thấyGiải thuậtBước 1: left = 1; right = N; //tìm kiếm tất cả các phần tử Bước 2: mid = (left+right)/2; // lấy mốc so sánh So sánh a[mid] với x, có 3 khả năng : a[mid] = x: Tìm thấy. Dừng a[mid] > x: //tìm tiếp x trong dãy con aleft .. amid -1 right =mid - 1;a[mid] < x: //tìm tiếp x trong dãy con amid +1 .. aright left = mid + 1; Bước 3: Nếu left <= right //còn phần tử chưa xét tìm tiếp. Lặp lại Bước 2. Ngược lại: Dừng //Ðã xét hết tất cả các phần tử.21int BinarySearch(int []a, int N, int x ){ int left =0; right = N-1; int mid; while (left <= right) { mid = (left + right)/2; if (x == a[mid]) return mid;//Thấy x tại mid if (x < a[mid]) right = mid -1; else left = mid +1; } return -1; // Tìm hết dãy mà không có x} Độ phức tạp tính toán cấp n: T(n)=O(log 2n)22Q & A23Bài tập 3Bổ sung vào lớp CMyIntArray:Phương thức phát sinh dãy số tăng dần, tiến hành so sánh (về số phép so sánh) của hai phương pháp tìm kiếm tuần tự và nhị phânPhương thức kiểm tra xem dãy số có thứ tự tăng/ giảm/ không có thứ tự để áp dụng phương pháp tìm kiếm nhị phân hay tuần tự cho phù hợp24Bài tập lý thuyếtLT1_1: Cho dãy số sau: Cho biết vị trí tìm thấy và số lần so sánh để tìm được phần tử có giá trị x = 6 khi áp dụng giải thuật tìm kiếm: tuyến tính và nhị phân LT1_2: Xây dựng giải thuật tìm kiếm phần tử có giá trị nhỏ nhất trong dãy số: Dùng mã tự nhiên, mã giả và lưu đồ25346612162134418012345678910Q & A26