Cấu trúc dữ liệu và giải thuật - Chương 5: Tìm kiếm - Ngô Quang Thạch

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT NGÔ QUANG THẠCH Email: thachnq@gmail.com ĐT: 01273984123 Chương 5: Tìm kiếm Tìm kiếm nhị phân Tìm kiếm tuyến tính Giới thiệu Giới thiệu Trong cuộc sống hàng ngày  Các hệ lưu trữ, hệ thống nội bộ, hệ thống bên ngoài  Quản lý dữ liệu, quản lý thông tin,  =>Tìm kiếm thường được thực hiện nhiều nhất để khai thác thông tin. Các thuật toán tìm kiếm được sử dụng được coi là các kỹ thuật cơ sở cho lập trình máy tính Giới thiệu Tìm kiếm một phần tử nào đó của một tập đối tượng theo một tiêu chí đề ra là bài toán phổ biến trong tin học  Tìm kiếm hồ sơ, lý lịch, tập tin,  Tìm kiếm thông tin, công văn, văn bản,  Giới thiệu Mô tả bài toán tìm kiếm: “cho một vec tơ A bao gồm n phần tử, có giá trị là các số khác nhau : A[1], A[2], A[3],, A[n]” “cho một số X, hãy tìm xem có phần tử nào của A mà giá trị của nó bằng X không” => Tìm kiếm sẽ “được thỏa” khi có, hoặc “không thỏa” khi không có phần tử nào có giá trị bằng X Các loại tìm kiếm 1. Tìm kiếm tuyến tính 2. Tìm kiếm nhị phân Tìm kiếm tuyến tính Giới thiệu phương pháp Tìm tuyến tính là một kỹ thuật tìm kiếm rất đơn giản và cổ điển. 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 dãy khó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. Tìm kiếm tuyến tính Các bước thực hiện ý tưởng giả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 Tìm kiếm tuyến tính Cài đặt thuật toán: int TimTuyenTinh(int a[],int n,int x) { int i=0 ; a[n]=x ; while(a[i] !=x) i++ ; if(i==n) return -1 ; else return i ; } Tìm kiếm tuyến tính Ví dụ minh họa Cho dãy số a: a = 12 2 8 5 1 6 4 15 Tìm x=6 Tìm kiếm tuyến tính 12 2 8 5 1 6 4 15X=6 12 2 8 5 1 6 4 15 Với i=0, a[0]=12 6 12 2 8 5 1 6 4 15 Với i=1, a[1]=2 6 12 2 8 5 1 6 4 15 Với i=2, a[2]=8 6 Tìm kiếm tuyến tính 12 2 8 5 1 6 4 15 Với i=3, a[3]=5 6 12 2 8 5 1 6 4 15 Với i=4, a[4]=1 6 12 2 8 5 1 6 4 15 Với i=5, a[5]=6 Dừng vòng lặp tìm kiếm tại vị trí i=5 Tìm kiếm tuyến tính Nhận xét: Dò tuần tự từng phần tử từ đầu đến cuối Thời gian tìm kiếm sẽ tốn nhiều thời gian hơn nếu phần tử nằm ở cuối danh sách Tìm kiếm nhị phân Giới thiệu phương pháp Nếu các phần tử của A đã được sắp xếp, thì tìm kiếm nhị phân là phương pháp tìm kiếm khá thông dụng (tương tự như cách thức ta hay làm như tra một từ trong từ điển). Đối với phép tìm kiếm nhị phân thì ta luôn chọn khoá ở giữa, giả sử dẫy đang xét là A1, ,A2 thì khoá ở giữa dãy sẽ là Ai với i= (l+r)/2.  Nếu X<Ai thì tìm kiếm được thực hiện tiếp với A1,,Ai-1;  Nếu ngược lại tìm kiếm lại được làm với Ai+1,,An Tìm kiếm nhị phân Các bước thực hiện ý tưởng giải thuật: Bước 1: left = 0; right = N-1; // tìm kiếm trên 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 a[left] .. a[mid -1] : right =mid - 1; + a[mid] < x: //tìm tiếp x trong dãy con a[mid +1] .. a[right] : 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ử Tìm kiếm nhị phân Cài đặt int Tim_nhi_phan (int a[] , int n , int x) { int left = 0 , right = n - 1 , mid; while (l<=r) { mid = (left+right)/2; if(a[mid] == x) return mid; else if(a[mid]<x) right = mid-1; else left = mid+1; } return -1; } Tìm kiếm nhị phân Ví dụ minh họa Cho dãy số a: a = 1 2 4 5 6 8 12 15 Tìm x=5, tìm x= 6, tìm x=11 Tìm kiếm tuyến tính 1 2 4 5 6 8 12 15X=5 1 2 4 5 6 8 12 15 left=0, right=7, mid=(0+7)/2=3, a[3]=5 =>Tìm được vị trí x=5 tại a[3] Tìm kiếm tuyến tính 1 2 4 5 6 8 12 15X=6 1 2 4 5 6 8 12 15 left=0, right=7, mid=(0+7)/2=3, a[3]=5 =>Tiếp tục tìm trong dãy con (a[4]..a[7]) Tìm kiếm nhị phân Tìm x=6 trong dãy con a[4]..a[7] left=4 right=7 mid=(4+7)/2=5 a[5]=8>6 =>Tìm x=6 trong dãy con a[4]..a[4] 1 2 4 5 6 8 12 15 Tìm kiếm nhị phân Tìm x=6 trong dãy con a[4]..a[4] left=4 right=4 mid=(4+4)/2=4 a[4]=6 =>Tìm được x=6 trong dãy con a[4]..a[4] 1 2 4 5 6 8 12 15 Tìm kiếm tuyến tính 1 2 4 5 6 8 12 15X=11 1 2 4 5 6 8 12 15 left=0, right=7, mid=(0+7)/2=3, a[3]=5 =>Tiếp tục tìm trong dãy con (a[4]..a[7]) Tìm kiếm nhị phân Tìm x=11 trong dãy con a[4]..a[7] left=4 right=7 mid=(4+7)/2=5 a[5]=8<11 =>Tiếp tục tìm x=11 trong dãy con a[6]..a[7] 1 2 4 5 6 8 12 15 Tìm kiếm nhị phân Tìm x=11 trong dãy con a[6]..a[7] left=6 right=7 mid=(6+7)/2=6 a[6]=12>11 =>Kết thúc Không tìm được x=11 trong dãy con a[6]..a[7] 1 2 4 5 6 8 12 15