Question

Question 3 Searching Algorithms [12 marks (4 marks) Define a method that when passed an array of integers arr and another integer target, returns the last index in arr where target exists and -1 if target isn't found in arr a. b. (4 marks) Provide a trace, in the form of a logic table, of running the following method for 1, 4, 4, 4, 5, 7, 8, 12, 12, 15, 16, 17, 35, 35, 35, 40 arr = target 14 The columns required for the logic table are provided below: arrmedian target first last first last median compared arrmedian] >) to or< or public static int binarySearch (int [ arr, int target) int first 0; arr.length -1 while (first < last) int last = (first last)/2; arr [median]) int median if (target F return median; if (target< arr [median]) last median 1; else 10 first median + 1; 11 -1; return 14 c. (4 marks) (Advanced) Determine the minimum number of searches (k) that must be performed on an array of size n to justify sorting it once (as- sume that the only algorithm available is selection sort) before performing k binary searches rather than performing k linear searches over an unsorted array

Answer 1

a. CODE

public static int linearSearch(int [] arr, int target)
    {
        int index = -1;
        for(int i = arr.length;i>=0;i--)
        {
            if(arr[i] == target)
            {
                index = i;
                break;
            }
        }
        return index;
    }

b.

first	last	first<=last	median	arr[median]	target compare
0	15	true	7	12	14>12
8	15	true	11	17	14<17
8	10	true	9	15	14<15
8	10	true	8	12	12>14
9	8	false

Since the loop terminates, -1 will be returned.