Give a sorted array of N elements, possibly with duplicates, find the number of

Question

Give a sorted array of N elements, possibly with duplicates, find the number of occurrences of an element k in O(log N) time. For example, given an array {1, 2, 3, 4, 5, 5, 6, 8, 9} and a number 5, we should return 2, since there are two occurrences of 5. Please complete the following method. It takes a sorted array and an integer, and returns the number of occurrences of that integer. Here we assume each number appears at most a constant number of times. You may assume the array is guaranteed to be sorted. Hint: modify binary search. public static int dupCount(int[] arr, int key) { }

Explanation / Answer

public static int srch(int a[],int start,int end,int key){ if(start>end) return -1; int mid = (start+end)/2; if(a[mid]== key){ return mid; } else{ if(a[start] a[mid]|| key a[mid] && key

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.