Given an array whose elements are sorted, return the index of a the first occurrence of a specific integer. Do this in sub-linear time. I.e. do not just go through each element searching for that element.

Question

vic · Accepted Answer

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?

Anonymous · Answer

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.

Anonymous · Answer

*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.

Sid · Answer

Binary Search will do this in O(log n)

Google

Google Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches