The first one is the best in general. Standard library choose it for the maximum flexibility in caller side. For example, you can .get() over HashMap<String, T> using &static str, which is not possible if the api follows the second or the third way.
Complexity is not something that can be easily measured on a single axis. While it may be more complex to read and understand the function signature it also makes usage of the function simpler. The complexity is also something just about every rust user is going to encounter since the standard collections use this technique. Diverging from the standard container API can actually add unnecessary complexity for users that are already familiar with those API's.
In terms of your range API, I would suggest you look at BTreeMap for inspiration. It has a similar range API, but rather than accepting two arguments it accepts anything that implements RangeBounds for the borrowed key. This provides a lot of flexibility.
@ggriffiniii thanks for the suggestion. The get() and range() APIs from std lib's collection was useful. Now llrb-index follow similar API giving importance to flexibility without compromising on performance.