CS Past Papers

2021 U2 Q2

vkungeLeave a comment

Part a) i)

In a linear search, each element of the array is traversed by using iteration.  Each element in the traversal is compared against a search key. If the key is found, the location of the array index is returned.  If the entire array is traversed without finding the key, dummy value is returned (e.g. -1)

(see this note [1])

Part b) ii)

In a binary search, an ordered list is searched for a key starting with the item at the middle of the list. If the item is not found at the location ,  a determination is made on which half of the list may contain the key, either the upper or lower half. This method is applied to search the midpoint of the half of the list which may contain the key.  This repeats until the key is found, or until the search space is reduced to a single location and  the list can no longer be divided into halves. If the key is found, the location of the element is returned, otherwise a dummy value is returned (e.g -1)

(see this note [2])

Part b)

    //Code to store values in array
    int arr[] =  {3,12,9,10,5,4}; 
    int arrayLength = sizeof(arr)/sizeof(int);
    
     //selection sort
    for ( int i = 0; i<arrayLength; ++i)
    {
        int smallest = i;
        for (int k = i  ; k<arrayLength; ++k)
        {
           if  (arr[k]<arr[smallest])
                smallest=k;
        }
        //if the first element was not the smallest,
        //swap the first item with the smallest
        if (smallest!=i)
        {
            int temp = arr[i];
            arr[i] = arr[smallest];
            arr[smallest]=temp;
        }
    }

Part c)

Search midpoint of [0-9], location 4, it is not the key, 16<27 so the left portion is searched

Search midpoint of [0-3], location 1, it is not the key, 16>9 so the right portion is searched

Search midpoint of [2-3], location 2, it is the key, thus the search function returns 2.

Further Explanation1

  1. First, the algorithm calculates the midpoint of the entire array’s index range. The array has 10 elements, indexed from 0 to 9. The midpoint is calculated as (low + high) / 2. Initially, low is 0 and high is 9, so the midpoint is (0 + 9) / 2 which equals 4.5. Since we are working with integer indices, we take the floor of this value to choose the lower index, resulting in 4. The value at index 4 is 27, which is greater than 16.
  2. Because 16 is less than 27, the algorithm ignores the right half of the array and recalculates the midpoint for the left subarray spanning from index 0 to 3. Now, low is 0 and high is 3, so the new midpoint is (0 + 3) / 2 which equals 1.5. Taking the floor of this value, we again choose the lower index, which is 1. The value at index 1 is 9, which is less than 16.
  3. The algorithm then focuses on the right subarray of the previous range, which is from index 2 to 3. The midpoint here is (2 + 3) / 2 which equals 2.5. After taking the floor, the midpoint is index 2. The value at index 2 is 16, which matches the key we are searching for.

The search concludes with the algorithm returning index 2 as the position where the key 16 is located in the array.

Footnotes

[1] https://islandclass.org/2020/09/01/linear-search/

[2] https://islandclass.org/2020/11/12/binary-search-implementation/

  1. TA Note ↩︎

Leave a comment