Welcome to Programming and Data Structures

Write int findLast(const vector<int>& vec, int key);. It should return the index where the last copy of key is found, or -1 if not found.

Warning: a logical approach is to start at the end and count down. If you want to be able to count down and reach -1, you should use an int for your index variable, not size_t. If a size_t is 0 and you subtract one, it wraps to the largest possible value. Or, if you use a size_t, you need to keep iterating while the index is “less than the size of the vector”.

Write int binarySearchSteps(const vector<int>& vec, int key);. It should return the number of values checked while doing binary search to find key, or to identify that it was not found.

You can use iteration or recursion, but it is intended that you use iteration. Each time you check the “middle” value, increment your count.

Write int binarySearchSteps(const vector<int>& vec, int key, int start, int end);. It should return the number of values checked while doing binary search to find key, or to identify that it was not found.

You must use recursion. while or for have been intentionally disabled.

Write void selectLargestToStart(vector<int>& vec, int n);. It should use a selection sort strategy to move the n largest values to the start of the vector.

Write void descendingInsertionSort(vector<int>& vec, int n);. It should do a descending (move the larger items to the front) insertion sort on the first n elements of vec.

We will consider the first element to be already sorted, so if n is 1 nothing will happen. n = 2 will do one pass of insertion sort, n = 3 will do two passes, and so on.

Write void descendingMerge(vector<int>& vec, vector<int>& temp, int start, int mid, int end);. It should do a descending (take the larger item first) merge of the elements of vec between start and end.

You can assume that the two halves (from start to mid and from mid + 1 to end) are already sorted in descending order. You should use the temp vector as temporary storage while merging.

Note that you should not assume that mid is always (start + end)/2. The two “halves” may be different sizes.

Write void descendingMergeSort(vector<int>& vec, vector<int>& temp, int start, int end);. It should do a descending (take the larger item first) merge of the elements of vec between start and end.

You should copy/paste your descendingMerge function here from Exercise 26.17.6.

Write int descendingPartition(vector<int>& vec, int start, int end);. It should do a partition of the elements of vec between start and end so that the elements greater than some pivot value come before the elements less than or equal to the pivot. It should return the index of the final location of the pivot.

Write int descendingQuicksort(vector<int>& vec, int start, int end);. It should do a quicksort of the elements of vec between start and end so that the elements greater than some pivot value come before the elements less than or equal to the pivot. It should return the index of the final location of the pivot.

You should copy/paste your descendingPartition function here from Exercise 26.17.8.