Bài 2: Kỹ thuật tìm kiếm (searching)

1Bài 2: Kỹ Thuật Tìm Kiếm (Searching) GV: Nguyễn Hữu Thể Khoa CNTT – Đại Học Cửu Long CTDL1- Nguyễn Hữu Thể 2 NỘI DUNG 1. Tìm kiếm tuyến tính1 2. Tìm kiếm nhị phân2 5 CTDL1- Nguyễn Hữu Thể 3 1. Tìm kiếm tuyến tính (sequential search)
Giải thuật − Thuật toán tiến hành so sánh x lần lượt 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ó khóa cần tìm, hoặc đã tìm hết mảng mà không thấy x. − Các bước tiến hành như sau : 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. CTDL1- Nguyễn Hữu Thể 4 1. Tìm kiếm tuyến tính (sequential search) int LinearSearch(int a[], int n, int x) { int i=0; while(i<n && a[i]!=x) i++; if (i<n) return i; // a[i] là phần tử có khoá x else return -1; // tìm hết mảng nhưng không có x } CTDL1- Nguyễn Hữu Thể 5 1. Tìm kiếm tuyến tính (sequential search) int LinearSearch(int a[], int n, int x) { for(int i=0;i<n; i++) { if (a[i]==x) return i; // a[i] là phần tử có khoá x } return -1; // tìm hết mảng nhưng không có x } CTDL1- Nguyễn Hữu Thể 6 1. Tìm kiếm tuyến tính (sequential search) − Ví dụ: Cho dãy số a 12 2 8 5 1 6 4 15 − Giá trị cần tìm: 8 i=0 i=1 i=2 CTDL1- Nguyễn Hữu Thể 7 1. Tìm kiếm tuyến tính (sequential search) 5 Khóa tìm 7 13 5 21 6 2 8 15 0 1 2 3 4 5 6 7 Vị trí = 2 Tìm thành công Số lần so sánh: 3 CTDL1- Nguyễn Hữu Thể 8 1. Tìm kiếm tuyến tính (sequential search) 9 7 13 5 21 6 2 8 15 0 1 2 3 4 5 6 7 Không tìm thấy Số lần so sánh: 8 Khóa tìm CTDL1- Nguyễn Hữu Thể 9 1. Tìm kiếm tuyến tính (sequential search) − Cải tiến cài đặt: dùng phương pháp “lính canh”  Đặt thêm một phần tử có giá trị x vào cuối mảng  Bảo đảm luôn tìm thấy x trong mảng  Sau đó dựa vào vị trí tìm thấy để kết luận. CTDL1- Nguyễn Hữu Thể 10 1. Tìm kiếm tuyến tính – pp “lính canh” int LinearSearch(int a[], int n, int x) { int i=0; // mảng gồm N phần tử từ a[0]..a[N-1] a[n] = x; // thêm lính canh vào cuối dãy (ptử thứ n+1) while(a[i]!=x) i++; if (i<n) return i; // a[i] là phần tử có khoá x else return -1; // tìm hết mảng nhưng không có x } CTDL1- Nguyễn Hữu Thể 11 1. Tìm kiếm tuyến tính (sequential search) − Đánh giá giải thuật: − Vậy giải thuật tìm tuần tự có độ phức tạp tính toán cấp n: T(n) = O(n) CTDL1- Nguyễn Hữu Thể 12 1. Tìm kiếm tuyến tính (sequential search) Nhận xét:  Giải thuật tìm tuyến tính không phụ thuộc vào thứ tự của các phần tử trong danh sách. CTDL1- Nguyễn Hữu Thể 13 2. Tìm kiếm nhị phân − Đối với những dãy đã có thứ tự (giả sử thứ tự tăng ), các phần tử trong dãy có quan hệ a[i-1] ≤ a[i] ≤ a[i+1] − Nếu x > a[i] thì x chỉ có thể xuất hiện trong đoạn [a[i+1] ,a[N]] của dãy − Nếu x < a[i] thì x chỉ có thể xuất hiện trong đoạn [a[0] ,a[i-1]] của dãy . CTDL1- Nguyễn Hữu Thể 14 2. Tìm kiếm nhị phân − Ý tưởng:  Tại mỗi bước tiến hành so sánh x với phần tử nằm ở vị trí giữa của dãy tìm kiếm hiện hành.  Dựa vào kết quả so sánh này để quyết định giới hạn dãy tìm kiếm ở bước kế tiếp là nửa trên hay nửa dưới của dãy tìm kiếm hiện hành CTDL1- Nguyễn Hữu Thể 15 2. Tìm kiếm nhị phân Bước 1: left = 1; right = N; Bước 2: mid = (left+right)/2; 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 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ử. CTDL1- Nguyễn Hữu Thể 16 2. Tìm kiếm nhị phân int BinarySearch(int a[],int n,int x ) { int left =0, right = n-1, mid; while (left <= right) { mid = (left + right)/2; if (x == a[mid]) return mid;//Tìm thấy x tại mid if (x < a[mid]) right = mid -1; else left = mid +1; } return -1; // trong dãy không có x } CTDL1- Nguyễn Hữu Thể 17 2. Tìm kiếm nhị phân 10 Khóa tìm 2 58 10 12 13 15 18 21 24 0 1 2 3 4 5 6 7 8 9 left rightmid CTDL1- Nguyễn Hữu Thể 18 2. Tìm kiếm nhị phân 10 Khóa tìm 2 58 10 12 13 15 18 21 24 0 1 2 3 4 5 6 7 8 9 left rightmid CTDL1- Nguyễn Hữu Thể 19 2. Tìm kiếm nhị phân 10 Khóa tìm 2 58 10 12 13 15 18 21 24 0 1 2 3 4 5 6 7 8 9 left right mid CTDL1- Nguyễn Hữu Thể 20 2. Tìm kiếm nhị phân 10 Khóa tìm 2 58 10 12 13 15 18 21 24 0 1 2 3 4 5 6 7 8 9 left right mid CTDL1- Nguyễn Hữu Thể 21 2. Tìm kiếm nhị phân 10 Khóa tìm 2 58 10 12 13 15 18 21 24 0 1 2 3 4 5 6 7 8 9 Vi trí = 3 Tìm thấy Số lần so sánh: 4 CTDL1- Nguyễn Hữu Thể 22 2. Tìm kiếm nhị phân int BinarySearch(int a[],int N,int x ) { int left =0, right = N-1; int mid; do{ mid = (left + right)/2; if (x = a[mid]) return mid; //Thấy x tại mid else if (x < a[mid]) right = mid -1; else left = mid +1; }while (left <= right); return -1; // Tìm hết dãy mà không có x } CTDL1- Nguyễn Hữu Thể 23 2. Tìm kiếm nhị phân − Đánh giá giải thuật: − Giải thuật tìm nhị phân có độ phức tạp tính toán cấp logn: T(n) = O(log 2 n) CTDL1- Nguyễn Hữu Thể 24 2. Tìm kiếm nhị phân Nhận xét:  Dựa vào quan hệ giá trị của các phần tử mảng để định hướng trong quá trình tìm kiếm  => chỉ áp dụng được cho những dãy đã có thứ tự.  Giải thuật tìm nhị phân tiết kiệm thời gian hơn rất nhiều so với giải thuật tìm tuần tự do Tnhị phân (n) = O(log 2 n) < Ttuần tự (n) = O(n). 25