Linear vs binary search: binary nhanh 1.125 lần, nhưng không phải lúc nào cũng nên dùng
Binary search O(log n) nghe là biết thắng linear O(n). Bài này đo thật trong go-lab: ở N=262.144, binary nhanh hơn 1.125 lần một lần tìm. Nhưng binary đòi mảng đã sắp — và chi phí sort trước (306 µs) đổi cục diện: nếu chỉ tìm 1-2 lần trên mảng chưa sắp, linear thắng. Cộng thêm yếu tố cache khiến ở N nhỏ binary chỉ nhỉnh 3,7 lần.