本文共 959 字，大约阅读时间需要 3 分钟。

Given a sorted array which contains scores range from 0 to 100. Write a program to find occurrence of given score.  eg. 1,1,1,40,40,40,100,100  input: 40  o/p : 3 (as 40 appear 3 times in array)

---------------------------------------------------------------------------------------------------------------------------------

Solution 1 : I said binary search for score in this example 40 which in turn will give and index and then have two pointer one goes left and one go right and count the 40. 

worst case O(n) if all numbers are 40.  Solution 2 : Modify the binary search such that when element does not exists it return s low index. and then do binary search 39.5 and 40.5 (score-0.5 and score +0.5)  searching 39.5 will give you index 2 which is one less than start index of 40.  searching 0.5 will give you index 6 which is one more than end index of 40.  He did not ask me to code this just want to have idea. I told him we need to handle some edge condition.

转载地址：http://jwboi.baihongyu.com/