The interesting thing about look is that it uses binary search, so it is much faster.
I also think your constant time claim sounds too strong. You can eat a lot of end of line search time after the binary search and still beat a linear/regex search.
As someone else pointed out, look can also exit sooner.