Trong các trường hợp khác nhau, ta thực hiện các lược đồ tìm kiếm khác nhau. Phần này so sánh hai kỹ thuật cơ bản: tìm kiếm tuần tự (sequential search) và tìm kiếm nhị phân (binary search).
| Tìm kiếm tuần tự (Sequential Search) | Tìm kiếm nhị phân (Binary Search) |
|---|---|
| Độ phức tạp thời gian O(n) | Độ phức tạp thời gian O(log n) |
| Tìm thấy khóa ở vị trí đầu tiên trong thời gian hằng số | Tìm thấy khóa ở vị trí giữa trong thời gian hằng số |
| Thứ tự phần tử trong container không ảnh hưởng | Các phần tử phải được sắp xếp trong container |
| Có thể triển khai bằng mảng và danh sách liên kết | Không thể triển khai trực tiếp trên linked list. Cần thay đổi quy tắc cơ bản của list |
| Thuật toán mang tính lặp (iterative) | Kỹ thuật Chia để trị (Divide and Conquer) |
| Dễ triển khai, ít code hơn | Phức tạp hơn, cần nhiều code hơn |
| Cần N lần so sánh cho trường hợp xấu nhất | Chỉ cần log n lần so sánh cho trường hợp xấu nhất |