Question

// return index i such that A[i] = x, return -1 if x is not found

int mysearch(A, left, right, x) {

//add statements

}

(a) (10 pts) Given a sorted array A of size n, i.e. data has been sorted. Give a Divide and Conquer recursive “mysearch” algorithm which first tests the element at position n/4 for equality with some value x, and then possibly checks the element at position 3n/4. The result is either discovering x or reducing the set size to a fraction of the original.

(b) (5 points) Give the recurrence equation of mysearch algorithm.

(c) (5 points) Give the best-case and worst-case runtime complexity of mysearch algorithm? Explain your answer

(d) (5 points) What is the average-case runtime complexity of mysearch algorithm? Explain your answer. Show transcribed image text // return index i such that A[i] = x, return -1 if x is not found int mysearch(A, left, right, x) { //add statements }

Answer 1

(a) Following is the implementation in C++

#include<iostream>
using namespace std;

// return index i such that A[i] = x
// return -1 if x is not found
int mysearch(int A[], int left, int right, int x)
{
        // Base case
        // The search space has been exhausted
        // return -1
        if(left > right)
                return -1;

        // Getting the index of n/4 element
        int mid1 = left + (right - left) / 4;

        // Getting the index of 3n/4 element
        int mid2 = right - (right - left) / 4;

        // If the element is equal to the n/4th element
        // return it's index
        if (A[mid1] == x)
                return mid1;

        // If the element is equal to the (3n/4)th element
        // return it's index
        if (A[mid2] == x)
                return mid2;

        // If the element is less than the (n/4)th element
        // recur to the first quarter of the array
        if (x < A[mid1])
                return mysearch(A, left, mid1 - 1, x);

        // If the element is greater than the (3n/4)th element
        // recur to the fourth quarter of the array
        else if (x > A[mid2])
                return mysearch(A, mid2 + 1, right, x);

        // Recur to the middle portion of the array
        else
                return mysearch(A, mid1 + 1, mid2 - 1, x);
}

// Driver code
int main()
{
        int n = 5;
        int A[n] = {1, 2, 3, 4, 5};
        cout << mysearch(A, 0, n - 1, 1);
        return 0; 
}

(b) The recurrence relation

(c)

The best case of this algorithm is when the first comparison/guess is correct. It means, regardless of the size of the array, we'll always get the result in constant time. So the best case complexity is O(1).

The worst case of this algorithm is when the middle element has to be found. It means, every time the search space would reduce to half it's size

Solving the above recurrence, we get,

(d)

The average case of this algorithm can be computed by taking the average of the number of iterations required if an element is at any position belonging to [0, 1, ........, n-1] respectively

To be more clear,

As evident from the tree structure above,

Number of nodes at level i = 3ⁱ

At every level, 2 matches can be done (at index n/4 and index 3n/4)