7. Analyze the following algorithm: int first = 0, last = n - 1, pivot; boolean

Question

7. Analyze the following algorithm:

int first = 0, last = n - 1, pivot;

boolean found = false;
while (first <= last && !found)
{
    pivot = (first + last) / 2;
    if (array[pivot] == item) found = true;
    else
        if (item < array[pivot]) last = pivot - 1;
        else first = pivot + 1;
}

if (found ) System.out.println("item found");
else System.out.println("item not found");

What is the technique used to search for the key item? Why?

8. Consider the following binary tree. What is the preorder sequence of this binary tree?

9. Consider the following array. Suppose that the array will be sorted using quicksort.

         location=     0     1    2    3    4    5    6    7    8    9
array[location]=   24   17   23   12   9    7   19   15   21   3

If the initial pivot is 17, what will be the location of the pivot after the first iteration of the algorithm is completed? Why?

Explanation / Answer

7. Analyze the following algorithm:
        int first = 0, last = n - 1, pivot;
        boolean found = false;
       while (first <= last && !found)
       {
           pivot = (first + last) / 2;
           if (array[pivot] == item) found = true;
           else
            if (item < array[pivot]) last = pivot - 1;
                else first = pivot + 1;
        }
        if (found ) System.out.println("item found");
        else System.out.println("item not found");

        THIS IS BINARY SEARCH.
        we are calculation pivot and trying to search for an item till item is found or first <=last.

       and then we are truncating the search bandwidth.
        thus THIS IS BINARY SEARCH.
       

8. Consider the following binary tree. What is the preorder sequence of this binary tree?
Binary Tree Traversal

TREE IS MISSING !! please provide tree will do preorder for that TREE.

9. Consider the following array. Suppose that the array will be sorted using quicksort.
         location=     0     1    2    3    4    5    6    7     8    9
array[location]=       24   17   23   12   9    7   19   15   21    3

if pivot is 17.

12 9 7 15 3 [17] 24 23 19 21

location of pivot is 5th location means (a[4])

in Quick SORT, array elements less than pivot will be moved to front. while array elements more than pivot will moved to last.

thus. 17 will be at 5th location.

Related Questions

Navigate

• Browse (All)
• Browse 7
• Subjects

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