Sự khác biệt giữa Tìm kiếm nhị phân và Tìm kiếm tuyến tính

Tìm kiếm nhị phân so với Tìm kiếm tuyến tính

Tìm kiếm tuyến tính, còn được gọi là tìm kiếm tuần tự là thuật toán tìm kiếm đơn giản nhất. Nó tìm kiếm một giá trị được chỉ định trong danh sách bằng cách kiểm tra mọi phần tử trong danh sách. Tìm kiếm nhị phân cũng là một phương pháp được sử dụng để định vị một giá trị được chỉ định trong danh sách được sắp xếp. Phương pháp tìm kiếm nhị phân giảm một nửa số phần tử được kiểm tra (trong mỗi lần lặp), giảm thời gian thực hiện để xác định mục đã cho trong danh sách.

Tìm kiếm tuyến tính là gì?

Tìm kiếm tuyến tính là phương pháp tìm kiếm đơn giản nhất, kiểm tra từng phần tử trong danh sách một cách tuần tự cho đến khi tìm thấy phần tử được chỉ định. Đầu vào của phương thức tìm kiếm tuyến tính là một chuỗi (chẳng hạn như một mảng, bộ sưu tập hoặc chuỗi) và mục cần tìm kiếm. Đầu ra là đúng nếu mục được chỉ định nằm trong chuỗi được cung cấp hoặc sai nếu nó không nằm trong chuỗi. Vì phương thức này kiểm tra mọi mục trong danh sách cho đến khi tìm thấy mục được chỉ định, trong trường hợp xấu nhất, nó sẽ đi qua tất cả các phần tử trong danh sách trước khi tìm thấy phần tử cần thiết. Độ phức tạp của tìm kiếm tuyến tính là o (n). Do đó, nó được coi là quá chậm để được sử dụng khi tìm kiếm các yếu tố trong danh sách lớn. Nhưng điều này rất đơn giản và dễ thực hiện.

Tìm kiếm nhị phân là gì?

Tìm kiếm nhị phân cũng là một phương pháp được sử dụng để định vị một mục được chỉ định trong danh sách được sắp xếp. Phương pháp này bắt đầu bằng cách so sánh phần tử được tìm kiếm với các phần tử ở giữa danh sách. Nếu so sánh xác định rằng hai phần tử bằng nhau, phương thức dừng lại và trả về vị trí của phần tử. Nếu phần tử được tìm kiếm lớn hơn phần tử ở giữa, nó sẽ khởi động lại phương thức chỉ bằng nửa dưới của danh sách được sắp xếp. Nếu phần tử được tìm kiếm nhỏ hơn phần tử ở giữa, nó sẽ khởi động lại phương thức chỉ bằng nửa trên của danh sách được sắp xếp. Nếu phần tử được tìm kiếm không nằm trong danh sách, phương thức sẽ trả về một giá trị duy nhất cho biết điều đó. Do đó, phương pháp tìm kiếm nhị phân giảm một nửa số phần tử được so sánh (trong mỗi lần lặp), tùy thuộc vào kết quả so sánh. Do đó, tìm kiếm nhị phân chạy trong thời gian logarit dẫn đến hiệu suất trường hợp trung bình o (log n).

Sự khác biệt giữa Tìm kiếm nhị phân và Tìm kiếm tuyến tính là gì?

Mặc dù cả tìm kiếm tuyến tính và tìm kiếm nhị phân đều là phương pháp tìm kiếm nhưng chúng có một số khác biệt. Trong khi tìm kiếm nhị phân hoạt động trên các danh sách được sắp xếp, tìm kiếm lót cũng có thể hoạt động trên các danh sách chưa sắp xếp. Sắp xếp một danh sách thường có độ phức tạp trung bình của n log n. tìm kiếm tuyến tính là đơn giản và dễ thực hiện hơn so với tìm kiếm nhị phân. Nhưng, tìm kiếm tuyến tính quá chậm để được sử dụng với các danh sách lớn do hiệu suất trường hợp trung bình o (n) của nó. Mặt khác, tìm kiếm nhị phân được coi là một phương pháp hiệu quả hơn có thể được sử dụng với các danh sách lớn. Nhưng việc thực hiện tìm kiếm nhị phân có thể khá khó khăn và một nghiên cứu đã chỉ ra rằng mã chính xác cho tìm kiếm nhị phân chỉ có thể được tìm thấy trong năm trong số hai mươi cuốn sách.