algorithm - Efficient way to count occurrences of a key in a sorted array -

this asked in on-site microsoft interview.

count number of occurrences of given key in array.

i answered linear search because elements may scattered in array. key found in beginning , @ end. need scan entire array.

next asked if array sorted?

thought while , said i'll use linear search again. because repetitions of key if present can anywhere in array. optimization said if first , last array elements same can take array length answer.

is analysis correct in both cases?

example:

input = [0 0 1 1 1 2 2 3 3], key = 1, answer = 3 input = [0 0 2 2 3 3],       key = 1, answer = 0 

for unsorted array there not can other linear search.

for sorted array can in o(logn) using modified binary search:

• find index of first occurrence of key, call f.
• find index of last occurrence of key, call l.
• if key exists in array l-f+1 answer.

finding first occurrence:

arr[i] first occurrence of key iff

• arr[i] == key and either
  • i == 0 ( it's first element of array) or
  • arr[i-1] != key (it's not first element of array , element it's left different)

you can modify binary search find first occurrence.
in binary search terminate search when find arr[mid] == key.
modify condition such terminate search when find first occurrence instead of any occurrence.

algorithm:

low = 0 high = arrsize - 1   while low <=  high    mid = (low + high) / 2    //if arr[mid] == key         // change   if arr[mid] == key , ( mid == 0 or arr[mid-1] != key )     return mid   //else if ( key < arr[mid] ) // change   else if ( key <= arr[mid] )      high = mid - 1   else     low = mid + 1           end-if  end-while  return -1 

similarly can find last occurrence.