Hello I have a homework could you please help me? My homework is: Problem: You a

Question

Hello I have a homework could you please help me? My homework is:

Problem: You are asked to implement a modified version of Binary Search on a given sorted array. However, besides searching for the given item, the modified version of Binary Search must return the number of occurences of the item in the array as below examples.

a-) Write the code for this modified version of binary search and test it with the example array. (Data Structures using C++)

b-) What would be the time complexity for worst case.

Example-1:

Assume that you are given the above array, the modified version of Binary Search will output 4 for the search item 44.

Example-2:

Assume that you are given the above array, the modified version of Binary Search will output 2 for the search item 50.

Example-3:

Assume that you are given the above array, the modified version of Binary Search will output 1 for the search item 66.

Example-4:

Assume that you are given the above array, the modified version of Binary Search will output 0 for the search item 13.

(Note: 2 of examples are enough for me then I can do the rest of examples)

sincereley..

Explanation / Answer

1) Use Binary search to get index of the first occurrence of x in arr[]. Let the index of the first occurrence be i.
2) Use Binary search to get index of the last occurrence of x in arr[]. Let the index of the last occurrence be j.
3) Return (j – i + 1);

#include<iostream>

using namespace std;

int count(int arr[], int x, int n);
int first(int arr[], int low, int high, int x, int n);
int last(int arr[], int low, int high, int x, int n);

/* driver program to test above functions */
int main()
{
int arr[] = {10, 14, 44, 44, 44, 44, 50, 50, 55, 66};
  
int x = 44; // Element to be counted in arr[]
int n = sizeof(arr)/sizeof(arr[0]);
int c = count(arr, x, n);
  
cout<<x<<" occurs "<<c<<" times"<<endl;

return 0;
}

/* 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; // index of first occurrence of x in arr[0..n-1]
int j; // index of last occurrence of x in arr[0..n-1]

/* get the index of first occurrence of x */
i = first(arr, 0, n-1, x, n);

/* If x doesn't exist in arr[] then return -1 */
if(i == -1)
return 0;
  
/* Else get the index of last occurrence of x. Note that we
are only looking in the subarray after first occurrence */
j = last(arr, i, n-1, x, n);   
  
/* return count */
return j-i+1;
}

/* if x is present in arr[] then returns the index of FIRST occurrence
of x in arr[0..n-1], otherwise returns -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;
}


/* if x is present in arr[] then returns the index of LAST occurrence
of x in arr[0..n-1], otherwise returns -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 < arr[mid+1]) && arr[mid] == x )
return mid;
else if(x < arr[mid])
return last(arr, low, (mid -1), x, n);
else
return last(arr, (mid + 1), high, x, n);
}
return -1;
}

/*

Output:

44 occurs 4 times

*/

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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