This is true, if your comparison operator is very expensive you should (very, very carefully) implement the traditional binary search.