To respond to Sid's comment: Binary search is the way to go, but you do need a slight modification, coz a simple binary search may not necessarily return the index of the first occurence, e.g. given input array 7777777777, what would a simple search return? The trick would be to seek to the left if the index at the middle of the current partition is the element you are looking for. The performance would depend on how many duplicates there are on average + log n If this average is n as in the above example you are looking at O(n/2), but then if you knew that already you could simply return the first element :) Anyone have a better idea?

*I left out an important part. You need to modify the binary search for the case that there's more than one instance of target-1. If you are at a node that matches your search and the right and the item at the next index also matches, move to the right child and continue searching.

binary search for target.-1. At the last step remember where you were checking even if you don't find it. If the element is target this is the first one. Otherwise it is in the next index of the array.