Bài giảng Cấu trúc dữ liệu và giải thuật: Giải thuật tìm kiếm trình bày các nội dung sau: Còn gọi là tuyến tính – Linear search, danh sách chưa sắp xếp hoặc đã sắp xếp, thời gian tỉ lệ với n (số phần tử), độ phức tạp O(n),. | TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH Cấu trúc dữ liệu và giải thuật Giải thuật tìm kiếm TS. Ngô Hữu Dũng Tìm kiếm – Searching Tìm kiếm tuần tự - Sequential search Tìm kiếm nhị phân – Binary search 2 Còn gọi là tuyến tính – Linear search Danh sách chưa sắp xếp hoặc đã sắp xếp Thời gian tỉ lệ với n (số phần tử) Độ phức tạp O(n) Danh sách đã sắp xếp Thời gian tỉ lệ với log2 n Độ phức tạp O(log n) Cấu trúc dữ liệu và giải thuật - Tìm kiếm Sequential search Duyệt danh sách từ đầu đến cuối 3 Dừng khi tìm thấy hoặc kết thúc danh sách Nếu tìm thấy: Trả về kết quả tìm thấy True hoặc vị trí được tìm thấy hoặc thông báo Nếu không tìm thấy: Trả về kết quả không tìm thấy False hoặc một giá trị như -1 hoặc thông báo Cấu trúc dữ liệu và giải thuật - Tìm kiếm Sequential search – Vòng lặp Trả về vị trí khi tìm thấy Trả về -1 khi không tìm thấy Lưu ý: Các code chỉ mang tính minh hoạ cho giải thuật Có nhiều cách diễn đạt và cải tiến thuật toán 1. int linearSearch(int a[], int n, int x) 2. { 3. int i; 4. for(i=0; i
