Can we use maps for searching instead of binary search?
As the exact running time will depend on the length and type of the keys, their distribution, their number, it is advisable to benchmark for your particular application.
Maps give O(1) look-up. Can't we go through the array once and build a map corresponding to its index (the opposite of array) and when we want to search something we can call map[VALUE] and it will return the index.
It might not work for large values in array but assuming a[i]<10^5, can't we do this instead of binary search? Then, each query will be O(1). 
P.S: i did mean unordered map..