Write an iterative version and a recursive version of function OCCURS that deter

Question

Write an iterative version and a recursive version of function OCCURS that determines how many times an integer value x occurs in array a[0..na-1]. Write a main program that illustrates the work of your functions. E.g., if a[ ]={1,2,3,3,4,5} then 3 occurs 2 times and 7 occurs 0 times.

Explanation / Answer

Using binary tree approach : /* if x is present in arr[] then returns the count of occurrences of x, otherwise returns -1. */ int count(int arr[], int x, int n) { int i; int j; i = first(arr, 0, n-1, x, n); if(i == -1) return i; j = last(arr, i, n-1, x, n); return j-i+1; } int first(int arr[], int low, int high, int x, int n) { if(high >= low) { int mid = (low + high)/2; /*low + (high - low)/2;*/ if( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x) return mid; else if(x > arr[mid]) return first(arr, (mid + 1), high, x, n); else return first(arr, low, (mid -1), x, n); } return -1; } int last(int arr[], int low, int high, int x, int n) { if(high >= low) { int mid = (low + high)/2; /*low + (high - low)/2;*/ if( ( mid == n-1 || x

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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