If you don't have this basic linux utility, you can use
grep '^string' file.txt
but there's a greater chance of having look installed than grep. grep '^string' file.txt
but there's a greater chance of having look installed than grep.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.