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 để xác định 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 làm 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 cần thiết để xác định vị trí 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 tuần tự từng phần tử trong danh sách cho đến khi tìm thấy một phần tử được chỉ định. Đầu vào cho phương pháp tìm kiếm tuyến tính là một chuỗi (chẳng hạn như mảng, tập hợp hoặc chuỗi) và mục cần được tìm kiếm. Kết quả đầu ra là true nếu mục được chỉ định nằm trong chuỗi đã cho hoặc sai nếu nó không nằm trong chuỗi. Vì phương pháp 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, nên 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 phần tử trong danh sách lớn. Nhưng điều này rất đơn giản và dễ thực hiện hơ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 để xác định vị trí một mục cụ thể trong danh sách đã 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 phép so sánh xác định rằng hai phần tử bằng nhau, phương thức sẽ dừng 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ẽ bắt đầu lại phương thức chỉ bằng cách sử dụng nửa dưới của danh sách đã sắp xếp. Nếu phần tử được tìm kiếm nhỏ hơn phần tử ở giữa, nó sẽ bắt đầu lại phương thức chỉ bằng cách sử dụng nửa trên cùng của danh sách đã 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ả của phép so sánh. Do đó, tìm kiếm nhị phân chạy theo 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à những phương pháp tìm kiếm nhưng chúng có một số điểm khác biệt. Trong khi tìm kiếm nhị phân hoạt động trên danh sách được sắp xếp, tìm kiếm lót cũng có thể hoạt động trên danh sách không được sắp xếp. Sắp xếp một danh sách thường có độ phức tạp trường hợp trung bình là n log n. tìm kiếm tuyến tính đơn giản và dễ thực hiện hơn so với tìm kiếm nhị phân. Tuy nhiên, tìm kiếm tuyến tính quá chậm để được sử dụng với 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 triển khai tìm kiếm nhị phân có thể khá phức tạp 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.
