3.1 We studied linear search, which searches an array A for an element Key by st

Question

3.1 We studied linear search, which searches an array A for an element Key by starting at index 0 and proceeding to look in indices 1, 2, 3, ..., Size-1 for Key. Write the code for a function int ReverseLinearSearch(int pArray[], int pSize, int pKey) which searches pArray for pKey in reverse order, i.e., starting at pSize-1 and working down to 0. The function shall return the index of pKey or -1 if pKey is not found. 3.2 Suppose we have a two-dimensional array of doubles named pArray with NUM_ROWS rows and NUM_COLS columns, where NUM_ ROWS and NUM_COLS are integer constants defined elsewhere. We wish to perform a search of pArray to locate an element pKey. Write a function void LinearSearch2D(double pArray[][NUM_COLS], double pKey, int& pRow, int& pCol) which searches pArray for pKey and "returns as output parameters" the row and column of pKey in the reference variables pRow and pCol. If pKey is not found, then pRow and pCol shall each be set to -1. Assume the elements of pArray are unique. 3.3 Binary search requires the elements of the array being searched to be ___. 3.4 Let A be an array of ints initialized to [13, 17, 29, 33, 41, 53, 84, 112, 167, 222, 341, 876] where the first element, A[0], is 13. During each pass of the loop in binary search, we compare the element at A[Middle] to see if it is equal to Key (the element being searched for). For this exercise, assume Key is 17. Answer these questions. (a) What values are Low and High initialized to? (b) For each pass of the while loop, list the values of Low, Middle, and High at the time that A[Middle] is compared to Key. (c) How many times will A[Middle] be compare to Key before Key is found? 3.5 Study the code in the Sorter class that I posted on the course website. Let A be an array of ints initialized to [40, 90, 60, 80, 20, 10, 70, 30, 50] where the first element, A[0], is 40. During each pass of the Bubble Sort sorting algorithm, pairwise elements are compared and swapped when they are out of order. Assume we are sorting A into ascending order. (a) Show the contents of A before the "compare adjacent elements operation" is performed during each pass of the for loop on Line 33. (b) How many times will the "compare adjacent elements operation" be performed before A is sorted? 3.6 Let A be the same unsorted array as in the previous exercise. During each pass of the Selection Sort sorting algorithm we locate the minimum element (at indices greater than or equal to pStartIndex) in the array and move it to its correct location. Assume we are sorting A into ascending order. (a) Show the contents of A before each call to FindMinIndex() on Line 68. (b) How many passes will we make of the for loop in SelectionSort before the array is sorted?

Explanation / Answer

3.3 Binary search requires the elements of the array being searched to be _in sorted order__.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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