tailieunhanh - Bài giảng Tìm kiếm (searching)

Bài giảng Tìm kiếm (searching) do Lê Sỹ Vinh biên soạn sau đây sẽ trang bị cho các bạn những kiến thức về việc tìm kiếm trên danh sách và tìm kiếm trên văn bản. Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về lĩnh vực này. | Tìm ki m (searching) Lê S Vinh B môn Khoa H c Máy Tính – Khoa CNTT i H c Công Ngh - HQGHN Email: vinhbio@ Các v n Tìm ki m trên danh sách: Có m t danh sách các i tư ng A, tìm xem m t vào danh sách này hay không Ví d : – Tìm m t sinh viên – m t s i n tho i – Tìm 1 t trong t i n – Tìm 1 lo i hàng hóa i tư ng X có thu c Các v n Tìm ki m trên văn b n (text matching): Tim ki m s xu t hi n c a m t o n văn b n (1 t , 1 câu, 1 o n ) trong m t văn b n l n. o n văn b n có th xu t hi n chính xác ho c g n chính xác trong văn b n l n. Ví d – – Search and replace in editors Search engine (yahoo, google ) Tìm ki m trên danh sách Input: • Danh sách các i tư ng A = (a0, ,an) • i tư ng c n tìm X Output: • i: v trí xu t hi n c a tư ng X trong A (i = -1 n u X không xu t hi n) Thu t toán: Duy t l n lư t trên danh sách A và so sánh xem X có trong danh sách hay không. Nêu có tr l i v trí xu t hi n u tiên, n u không tr l i (-1) ph c t p: O(n) Tìm ki m trên danh sách ã ư c s p x p Input: • Danh sách các i tư ng ã ư c s p x p A = (a0, ,an) | ai ≤ ai+1 • i tư ng c n tìm X Output: i: v trí xu t hi n c a tư ng X trong A (i = -1 n u X không xu t hi n) Tìm ki 1. 2. 3. m nh phân: So sánh X v i ph n t gi a danh sách , n u N u b ng → X n m v trí gi a danh sách N u nh hơn, Tìm ki m X trên n a u c a danh sách N u l n hơn, Tìm ki m X trên n a cu i c a danh sách ph c t p: O (log .