The problem is to extend the binary search algorithm to find all occurrences of a target value in a sorted array in the most efficient way.
Concretely speaking, the input of the algorithm is (1) a sorted array of integers, where some numbers may appear more than once, and (2) a target integer to be searched. The output of the algorithm should be a pair of index values, indicating the first and last occurrence of the integer in the array, if it does occur.
The source code could be in c#, c, c++.
Also, what is the max and min number of comparisons that we might need to find the indexes?
See Question&Answers more detail:
os 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…