CareerCup

BTS?

maybe red and black BST is the solution?

may be binary search

BST is a good option. Maybe we can add 'occurrences' field to every node (to avoid creation of duplicate nodes.)

I would go for binary search.
BST has overhead associated with creation. Plus the run time run time for search in both BST and binary search in log n (I think not 100%)

Whether you choose array implementation or bst, your algorithm in any case run in O(log n).

Here is my take:
Create a hashtable of the array, the creation cost is O(n) but every other access can be done in O(n). But yes space complexity is O(n).

It is better than BST but yes space complexity not as good compared to BS. But yes every time search cost is O(1) which is not the case with BS for all inquiries ...

Using BST, is not really an option, because the input array is sorted. The BST, would be completely unbalanced and would effectively be like a singly linked list. (hence will give O(N) on search, not the proclaimed O(n log n)). You can try to shuffle the sorted array, but shuffling would also cost O(N).

I like ZooZoo solution, of O(1) search time complexity, O(N) creation time complexity, and O(N) space complexity

Now that I think of it, we can use a generalized version of divide-and-conquer search (instead of dividing by 2, as binary search, we can divide by m (>2)), depending upon (a[max-1]-a[0])/(some distribution/duplication related constant).

It will give a better than log(2,n) performance of Binary search.

We could do a counting sort. Each location will hold the count of the number of occurrences.
Example count[0] = 0, count[1] = 1, count[2] = 1, count[3] = 4..and so on.
Something like count[ ] = { 0,1,1,4,1,1,1,1,3,1}
The index of first occurrence can by created by
index[i] = index[i-1] + count[i-1]