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..
Here are the problems you might want to consider -
You can't store multiple elements of the same value in map
The lookup time is O(log(n)) and not O(1)
It's not magic that happens in map which allows us to access it in lesser time. There's an hashing process going on in the background in unordered_map which gives O(1)and that takes time as well. So, the big O hides a big constant time factor. Standard map gives you a O(logn) lookup, same time complexity as binary search in an array.
The average time complexity of searching you get is about the same. The main problem you will have using standard maps in C++ is that it won't be able to hold multiple elements that have same values. One advantage that you might get using map is the deletion and insertion time will be O(logn).
So, if you know that the dataset you will be working on doesn't have duplicate elements and/or there will be frequent addition/deletion of elements, then you can surely consider map as the better alternative in this case
A hash table, like a Python dictionary, will give amortized constant average cost per look up.
For large data sets this may become an interesting alternative to binary search.
Some algorithms may absolutely need a binary search for the following reason:
When the lookup value is not in the data set, a binary search can still tell what the least value is in the data set that is greater than the lookup value, and the greatest that is less, at the same O(logn) cost.
To me the matter of duplicates is less of an issue, as you could store tuples of (value, frequency) or (value, [payload1, payload2, ...]) in your array, and so still use a hash table.
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.
