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

Tìm ki m (searching)<br /> Lê S Vinh<br /> B môn Khoa H c Máy Tính – Khoa CNTT<br /> i H c Công Ngh - HQGHN<br /> Email: vinhbio@gmail.com<br /> <br /> Các v n<br /> Tìm ki m trên danh sách:<br /> Có m t danh sách các i tư ng A, tìm xem m t<br /> vào danh sách này hay không<br /> Ví d :<br /> – Tìm m t sinh viên<br /> – m t s i n tho i<br /> – Tìm 1 t trong t i n<br /> – Tìm 1 lo i hàng hóa<br /> <br /> i tư ng X có thu c<br /> <br /> Các v n<br /> Tìm ki m trên văn b n (text matching):<br /> 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…)<br /> 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<br /> g n chính xác trong văn b n l n.<br /> Ví d<br /> –<br /> –<br /> <br /> Search and replace in editors<br /> Search engine (yahoo, google…)<br /> <br /> Tìm ki m trên danh sách<br /> Input:<br /> • Danh sách các i tư ng A = (a0,…,an)<br /> •<br /> i tư ng c n tìm X<br /> Output:<br /> • 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)<br /> <br /> 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<br /> 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)<br /> ph c t p: O(n)<br /> <br /> Tìm ki m trên danh sách ã ư c s p x p<br /> Input:<br /> • Danh sách các i tư ng ã ư c s p x p A = (a0,…,an) | ai ≤ ai+1<br /> •<br /> i tư ng c n tìm X<br /> Output:<br /> 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)<br /> Tìm ki<br /> 1.<br /> 2.<br /> 3.<br /> <br /> m nh phân: So sánh X v i ph n t<br /> gi a danh sách , n u<br /> N u b ng → X n m v trí gi a danh sách<br /> N u nh hơn, Tìm ki m X trên n a u c a danh sách<br /> N u l n hơn, Tìm ki m X trên n a cu i c a danh sách<br /> <br /> ph c t p: O (log n)<br /> <br />