## VMWare Inc Interview Question

Software Engineer Interns**Team:**NSBU

**Country:**United States

**Interview Type:**Phone Interview

This problem is trap. If you perform binary search for n and once found, going in left and right direction till we see n results in worst case O(n) time (when entire array is filled with n). We don't want that, however arriving it this way is normal and interviewer will ask if there is better way.

Lets denote array indexes as L and R. Once found at mid, we should continue binary searches for start index of n. Once found, say s then we look for index of last n using binary search once more.

```
"""
Given a sorted array arr[] and a number x, write a function that counts the occurrences of x in arr[].
Expected time complexity is O(Logn)
"""
def occurrences(arr, num):
first = 0
last = 0
for idx, val in enumerate(arr):
if val == num:
first = idx
break
for idx, val in reversed(list(enumerate(arr))):
if val == num:
last = idx
break
occurrence = last-first+1
print "Number {} appeared {} times in {}.".format(num, occurrence, arr)
return occurrence
ip = [1, 1, 2, 2, 2, 2, 2, 3, 4]
occurrences(ip, 2)
```

This is how you will solve in C#:

```
// Count Occurrence of n in integer array arr.
public static int countOccurrence(int[] arr, int n) {
int first = binarySearch(arr, n, true);
if (first >= 0) {
int last = binarySearch(arr, n, false);
return last - first + 1;
}
return 0;
}
// Finding First or last occurrence of integer n in sorted integer array: arr, searchFirst= true means search first occurrence else search last occurrence.
// Return index location in array for given n either first or last index. If not found return -1.
public static int binarySearch(int[] arr, int n, bool searchFirst) {
int result = -1;
if (arr != null && arr.Length > 0) {
int low = 0, high = arr.Length - 1;
while (low<=high) {
int mid = low + (high-low)/2;
if (arr[mid] == n) {
result = mid;
if (searchFirst) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
else if (arr[mid] > n) {
high = mid-1;
}
else {
low = mid+1;
}
}
}
return result;
}
```

Overall time complexity is O(Log n)

}

- sivapraneethalli November 13, 2016