Binary search also possible


#1

You could use the binary search as well in this question. However, take extra care in handling the duplicates.