Chương 5: Thuật toán tìm kiếm - Cô Võ Thị Hường

Cấu trúc dữ liệu và giải thuật GV: Võ Thị Hường LOGO CÁC THUẬT TOÁN TÌM KIẾM 1 Thuật toán tìm kiếm tuần tự (Sequential Searching) 2 Thuật toán tìm kiếm nhị phân (không đệ quy) (Binary Searching) Bài toán tìm kiếm Đầu vào:  Dãy X, có n đối tượng, mỗi đối tượng có một “khóa tìm kiếm”  Khóa của đối tượng cần tìm (Key) Đầu ra:  Vị trí của đối tượng có khóa „Key’ trong dãy X nếu tìm kiếm thành công, ngược lại trả về 0. Thuật toán tìm kiếm tuần tự  Ý tưởng:  So sánh khóa của đối tượng cần tìm với khóa của đối tượng đầu tiên trong dãy.  • Nếu bằng nhau, kết thúc tìm kiếm (thành công) • Nếu không bằng, chuyển sang đối tượng kế tiếp Lặp lại công việc trên cho đến khi gặp một đối tượng có khóa bằng với khóa cần tìm (thành công) hoặc đã hết các đối tượng trong dãy (không thành) Thuật toán tìm kiếm tuần tự Ví dụ:  K = {5, 98, 24, 34, 46}  Tìm X1 = 24, X2 = 80 theo thuật toán tìm kiếm tuần tự Thuật toán tìm kiếm tuần tự K = {5, 98, 24, 34, 46} Tìm X1 = 24  Lần 1: Với i = 1, so sánh K[1]=5  X1, tiếp tục tìm tại vị trí i = 2  Lần 2: Với i = 2, so sánh K[2]=98  X1, tiếp tục tìm tại vị trí i = 3  Lần 3: Với i = 3, so sánh K[3] = X1, quá trình tìm kiếm kết thúc vì đã tìm thấy X1 tại vị trí thứ 3 trong dãy khóa Thuật toán tìm kiếm tuần tự  K = {5, 98, 24, 34, 46}, Tìm X1 = 80  Lần 1: Với i = 1, so sánh K[1]=5  X1, tiếp tục tìm tại vị trí i = 2  Lần 2: Với i = 2, so sánh K[2]=98  X1, tiếp tục tìm tại vị trí i = 3  Lần 3: Với i = 3, so sánh K[3]=24  X1, tiếp tục tìm tại vị trí i = 4  Lần 4: Với i = 4, so sánh K[4]=34  X1, tiếp tục tìm tại vị trí i = 5  Lần 5: Với i = 5, so sánh K[5]=46  X1, tiếp tục tìm tại vị trí i = 6  Với i=6 > n, quá trình tìm kiếm kết thúc mà không tìm thấy X1 trong dãy khóa Thuật toán tìm kiếm tuần tự  Giải thuật:  Input: Mảng A[1..n], giá trị X  Output: Chỉ số i  [1..n] mà tại đó A[i] = X Hoặc 0 nếu A[i]  X i  [1..n] Function TimKiemTuanTu (A: Mảng, n: Số phần tử, X: Khóa tìm kiếm) : chỉ số i = 1; while (A[i]  X) & (i  n) do i = i+1 if (i = n+1) then return 0; else return i; Thuật toán tìm kiếm nhị phân  Ý tưởng:  Ứng dụng cho dãy đã sắp xếp thứ tự  Kiểm tra phần tử giữa của dãy • Nếu khóa cần tìm nhỏ hơn thì tiến sang trái • Nếu trùng khớp thì kết thúc • Nếu khóa cần tìm lớn hơn thì tiến sang phải Thuật toán tìm kiếm nhị phân  Giải thuật:  Input: Mảng A[1..n] sắp xếp tăng dần, giá trị X  Output: Chỉ số i  [1..n] mà tại đó A[i] = X Hoặc 0 nếu A[i]  X i  [1..n] Function TimKiemNhiPhan (A, n, X) : chỉ số l = 1; r = n; while (l  r) do m = (l+r)/2; if (A[m] = X) then return m; else if (X < A[m]) then r = m-1; else l = m+1; return 0; Thuật toán tìm kiếm nhị phân Ví dụ:  K = {5, 98, 24, 34, 46}  Tìm X1 = 24, X2 = 80 theo thuật toán tìm kiếm nhị phân không đệ quy  Ví dụ 2.  Cho d·y khãa K: K={32, 43, 18, 80, 60, 59, 93, 70, 55}  Minh häa qu¸ tr×nh t×m kiÕm X1 = 80; X2 = 81 theo ph¬ng ph¸p t×m kiÕm nhÞ ph©n. Thuật toán tìm kiếm nhị phân Ksx = {5, 24, 34, 46, 98}, X1 = 24  Khởi đầu l = 1, r = 5 m = (l+r)/2 = (1+5)/2 = 3 X1 < K[3], tiếp tục tìm kiếm X1 trong dãy có l = 1, r = 2  l = 1, r = 2 m = (l+r)/2 = (1+2)/2 = 1 X1 > K[1], tiếp tục tìm kiếm X1 trong dãy có l = 2, r = 2  l = 2, r = 2 m = (l+r)/2 = (2+2)/2 = 2 X1 = K[2], quá trình tìm kiếm dừng lại vì đã tìm thấy X1 tại vị trí thứ 2 trong dãy đã được sắp xếp Thuật toán tìm kiếm nhị phân Ksx = {5, 24, 34, 46, 98}, X2 = 80  Khởi đầu l = 1, r = 5 m = (l+r)/2 = (1+5)/2 = 3 X2 > K[3], tiếp tục tìm kiếm X2 trong dãy có l = 4, r = 5  l = 4, r = 5 m = (l+r)/2 = (4+5)/2 = 4 X2 > K[4], tiếp tục tìm kiếm X2 trong dãy có l = 5, r = 5  l = 5, r = 5 m = (l+r)/2 = (5+5)/2 = 5 X2 > K[5], tiếp tục tìm kiếm X2 trong dãy có l = 5, r = 4  l = 5, r = 4 Thấy l > r nên quá trình tìm kiếm dừng lại mà không tìm thấy X2 trong dãy đã được sắp xếp LOGO