Question1: Consider the following two approaches to the binary search algorithm

Question

Question1:

Consider the following two approaches to the binary search algorithm using the STL vector:

Approach A

int BinarySearch(vector<int> A, int key)  
    {
    int l = 0;

    int r = A.size()-1;

    while (l <= r)  
        {

            int m = (l + r) / 2;  
            if (key < A[m])
            {
                r = m - 1;
            }
            else if (key > A[m])
            {
                l = m + 1;
            }
            else
            {

                return count;
            }
        }

        return -1;
    }  

Approach B

int search::BinarySearch(vector<int> sortedArray, int first, int last, int key)
    {
       if (first <= last) {
           int mid = (first + last) / 2;
           if (key == sortedArray[mid])
               return mid;
           else if (key < sortedArray[mid])
               return BinarySearch(sortedArray, first, mid-1, key);
           else
               return BinarySearch(sortedArray, mid+1, last, key);
       }
       return -1;
    }

Which approach uses recursion? Explain why Approach B has more parameters than Approach A.

C.

D.

Both Approach A and Approach B use recursion. The additional parameters are not necessary and should be removed to make the method implementation more readable.

Question 2:

Consider the following:

    int BinarySearch(int A[], int key, int low, int high)  
    {
  
        while (low <= high)  
        {
            int m = (low + high) / 2;
            if (key < A[m])
            {
                high = m - 1;
            }
            else if (key > A[m])
            {
                low = m + 1;
            }
            else
            {

                return m;
            }
        }

        return -1;
    }

What is the purpose of iteration in the above code?

To set the index point in the middle so the right hand side of the array can be searched before the left hand side is searched.

A. Approach B uses recursion. Approach B has first and last parameters because they are not defined locally in the method itself. Either defining these values in the parameters or locally in the method is a matter of preference and has no bearing on the outcome. These values are needed to define the search area, either by increasing the value of first or decreasing the value of last.

Explanation / Answer

Q1.

Answeris C. i.e. Approach B uses recursion. Approach B includes the additional first and last parameters because they are required in the process of recursion to reduce the search area, either by increasing the value of first or decreasing the value of last when a recursive call is made.

When key < sortedArray[mid], then value of last is decreased to mid-1

and when key > sortedArray[mid] then value of firstis increased to mid+1.

Q2. Answer is B. i.e. To search between the low and high index numbers as long as there are index numbers between low and high to search.

This algorithm iterates between low and high to search key and in each iteration it either increases value of low to (m+1) or decreases value of high to (m-1).

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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