Main Contents Page
CTEC1401 Programming in C
 Quick Reference
Week 18: Functions III
Week 19: Searching
 Week 20: Sorting

  1. Before the lab session read CFTTP Chapter 12 on searching and study the solved exercises 12.1 to 12.4 very carefully.

  2. linearsearch1

    Copy the following code into a file called linearsearch1.c. 

    #include<stdio.h>
#include<stdlib.h>

int linearSearch(int * a, int key, int size)
// returns the index of key in the array a or -1 if key is not found
{
    int i = 0, pos = 0, found = 0;
    
    while (!found && (i<size))
    {
        if (a[i] == key) {
           found = 1;
           pos = i;
        }
        else
           i++;
    }
    return found ? pos : -1;
}

main()
{
    int N;          /* how many numbers?         */
    int * nums;     /* where are they ?          */
    int i;          /* loop counter              */
    int key;        /* key to find               */
    int result;     /* result of search          */
    char option;    /* what the user wants to do */

    // Find out how many numbers are needed and dynamically allocate an array
     
    printf("How many numbers? ");
    scanf(" %i", &N);
    nums = malloc(N * sizeof(int));
    
    // Input the numbers one at a time from the standard input stream

    for (i=0; i<N; i++)
    {
        printf("nums[%d] ? ", i);
        scanf(" %i", &nums[i]);
    }

    // What would the user like to do?
    
    printf("Option: (f)ind number or (q)uit?");
    scanf(" %c", &option);
    while (option != 'q') {
        printf("Value to look for? ");
        scanf(" %i", &key);
        
        result = linearSearch(nums,key,N);
        if (result != -1)
           printf("Found %d at position %d\n", key, result);
        else
           printf("Key %d not found\n", key);
       
        printf("Option: (f)ind number or (q)uit?");
        scanf(" %c", &option);
  }
}

    Compile and run the program and make sure that you understand how it works. Note particularly the following points:

    • The use of the found flag in the linear search function. You should dry run this code on paper to check that you understand fully how it works.
    • The main program allocates memory for an array dynamically. This means that the memory is allocated at run-time rather than at compile-time. The reason for this is that you do not know until the user enters the size of the array how big it must be. Dynamic memory allocation is covered a little later in the module (and in more depth) but if you wish to read ahead you should look at how the function malloc works.
    • The main body of the program is a fairly straightforward loop that asks the user to enter a command and then responds. Please make sure you are happy with how this is working because this main program will be used as a basis and developed in a number of ways during subsequent exercises and over the next few weeks.

  3. linearsearch1a

    The previous question linearsearch1 showed you how to write a linear search function and a simple test program. Make a copy of this program linearsearch1a.c and modify the search algorithm so that it searches from the other end of the array. So, if we consider the previous algorithm as going from "left to right" then this one will do from "right to left". What this means is that if there is more than one occurrence of a key in the array then the highest index that contains that key will be returned.

  4. linearsearch2

    Copy the following code into a file called linearsearch2.c. 

    #include<stdio.h>
#include<stdlib.h>
#include <math.h>
#include <time.h>

#define DEFAULT_SIZE 100

int linearSearch(int * a, int key, int size)
// returns the index of key in the array a or -1 if key is not found
{
    int i = 0, pos = 0, found = 0;
    
    while (!found && (i<size))
    {
        if (a[i] == key) {
           found = 1;
           pos = i;
        }
        else
           i++;
    }
    return found ? pos : -1;
}

main(int argc, char ** argv)
{
    int N;          /* how many numbers?         */
    int modulo;
    int * nums;     /* where are they ?          */
    int i;          /* loop counter              */
    int key;        /* key to find               */
    int result;     /* result of search          */
    char option;    /* what the user wants to do */

    // Find out how many numbers are needed and dynamically allocate an array

    printf("To specify array size and seed the random number generator:\n");
    printf("%s <number> <seed>\t e.g. %s 10 47912\n",argv[0],argv[0]);    
    
    N =   (argc > 1) ? atoi(argv[1]) : DEFAULT_SIZE;
    srand((argc > 2) ? atoi(argv[2]) : clock());
    modulo = (int)(pow(10, (floor(log10(N))+1)));
    
    printf("Generating %i random numbers modulo %i\n", N, modulo);
    nums = (int*) malloc(sizeof(int)*N);
    for(i=0; i<N; i++)
        nums[i] = rand() % modulo;
    
    // Print out the randomly generated sequence
    for(i=0; i<N; i++)
        printf(" %i ", nums[i]);
    printf("\n");
            
    printf("Option: (f)ind number or (q)uit?");
    scanf(" %c", &option);
    while (option != 'q') {
        printf("Value to look for? ");
        scanf(" %i", &key);
        
        result = linearSearch(nums,key,N);
        if (result != -1)
           printf("Found %d at position %d\n", key, result);
        else
           printf("Key %d not found\n", key);
       
        printf("Option: (f)ind number or (q)uit?");
        scanf(" %c", &option);
  }
}

    The code contains some advanced features in order to perform its function. Therefore, please the following points:

    • The linear search algorithm is the same one that you have seen before. All that is different is the main program.
    • The main program generates an array using a random number generator. It uses a default array size of 100 (look at the #define at the top of the program.) This can be changed when you run the program by providing a command line argument like this: 
          ./linearsearch2 50
      This would create an array of size 50 and populate it with 50 random values. Feel free to inspect the code that creates the array and populates it with the random numbers - it would be useful to get an idea of how this works but it is not essential to complete the exercise.
    • The main loop within the program is once again fairly straightforward allowing the user to enter a key to search for and responding with an appropriate message.

    Compile and run the program. Try out different sizes of array.

  5. binarysearch1

    Copy the following code into a file called binarysearch1.c. 

    #include<stdio.h>
#include<stdlib.h>
#include <math.h>
#include <time.h>

#define DEFAULT_SIZE 100

#ifdef TICKS
int tick(int i) { printf("<%d>",i); return 1; }
#endif

inline void SWAP(int *a, int j, int k)
{
    if (j!=k) {a[j] ^= a[k]; a[k] ^= a[j]; a[j] ^= a[k];}
}

/*
 * Sort the array a with size N using a BUBBLE SORT algorithm
 * NB - This is a simple algorithm to understand but is one of the
 * worst sorting algorithms there is in terms of performance
 */
void bubbleSort( int a[], int N )
{
    int i,j;
    for (i=N-1; i>0; i--)
        for (j=0; j<i; j++)
            if (a[j] > a[j+1])
                SWAP(a,j,j+1);
}

int binarySearch(int * a, int key, int size)
// returns the index of key in the array a or -1 if key is not found
{
    int lo=0, hi=size-1, pos=0, found=0, mid=0;
  
    while ((lo<=hi) && !found)
    {
        mid = (lo + hi) / 2;
        
        #ifdef TICKS
        tick(a[mid]);
        #endif

        if (a[mid] == key) {
           found = 1;
           pos = mid;
        }
        else if (a[mid] < key)
           lo = mid+1;
        else
           hi = mid-1;
    }
    return found ? pos : -1; 
}

main(int argc, char ** argv)
{
    int N;          /* how many numbers?         */
    int modulo;
    int * nums;     /* where are they ?          */
    int i;          /* loop counter              */
    int key;        /* key to find               */
    int result;     /* result of search          */
    char option;    /* what the user wants to do */

    // Find out how many numbers are needed and dynamically allocate an array

    printf("To specify array size and seed the random number generator:\n");
    printf("%s <number> <seed>\t e.g. %s 10 47912\n",argv[0],argv[0]);    
    
    N =   (argc > 1) ? atoi(argv[1]) : DEFAULT_SIZE;
    srand((argc > 2) ? atoi(argv[2]) : clock());
    modulo = (int)(pow(10, (floor(log10(N))+1)));
    
    printf("Generating %i random numbers modulo %i\n", N, modulo);
    nums = (int*) malloc(sizeof(int)*N);
    for(i=0; i<N; i++)
        nums[i] = rand() % modulo;
    bubbleSort(nums,N);
    
    // Print out the (sorted) randomly generated sequence
    for(i=0; i<N; i++)
        printf(" %i ", nums[i]);
    printf("\n");
            
    printf("Option: (f)ind number or (q)uit?");
    scanf(" %c", &option);
    while (option != 'q') {
        printf("Value to look for? ");
        scanf(" %i", &key);
        
        result = binarySearch(nums,key,N);
        if (result != -1)
           printf("Found %d at position %d\n", key, result);
        else
           printf("Key %d not found\n", key);
       
        printf("Option: (f)ind number or (q)uit?");
        scanf(" %c", &option);
  }
}

    This time the search algorithm uses a binary search technique. This technique relies upon the list of values being maintained in ascending numerical order. A completely random sequence is not necessarily in order so we must sort the array before performing any searches.

    Note that the material on sorting comes a little later. So, for now, just accept that the bubble sort function provided does the required job. By the way, bubble sort is not really a very efficient sorting algorithm, but it is quite easy to follow - this is why we have used it here. Even though you may not have covered sorting algorithms formally, you may find this algorithm reasonably easy to understand.

    Compile and run the program. Use the compiler flag to switch on the ticks. 

        gcc binarysearch1.c -DTICKS -o binarysearch1
    Notice how the search performance is so much better with this algorithm than with the linear algorithm you looked at earlier. The ticks will give you a dramatic visual representation of this. (E.g. run the program and specify an array size of ten thousand and then search for the last item in the (sorted) list. Then go back to linearsearch3 and repeat the experiment with an array of ten thousand elements and search for the last item.

    6. Supplementary Exercises

  6. linearsearch3

    Copy the following code into a file called linearsearch3.c. 

    #include<stdio.h>
#include<stdlib.h>
#include <math.h>
#include <time.h>

#define DEFAULT_SIZE 100

#ifdef TICKS
int tick(int i) { printf("<%d>",i); return 1; }
#endif

int linearSearch(int * a, int key, int size)
// returns the index of key in the array a or -1 if key is not found
{
    int i = 0, pos = 0, found = 0;
    
    while (!found && (i<size))
    {
        #ifdef TICKS
        tick(a[i]);
        #endif
        if (a[i] == key) {
           found = 1;
           pos = i;
        }
        else
           i++;
    }
    return found ? pos : -1;
}

main(int argc, char ** argv)
{
    int N;          /* how many numbers?         */
    int modulo;
    int * nums;     /* where are they ?          */
    int i;          /* loop counter              */
    int key;        /* key to find               */
    int result;     /* result of search          */
    char option;    /* what the user wants to do */

    // Find out how many numbers are needed and dynamically allocate an array

    printf("To specify array size and seed the random number generator:\n");
    printf("%s <number> <seed>\t e.g. %s 10 47912\n",argv[0],argv[0]);    
    
    N =   (argc > 1) ? atoi(argv[1]) : DEFAULT_SIZE;
    srand((argc > 2) ? atoi(argv[2]) : clock());
    modulo = (int)(pow(10, (floor(log10(N))+1)));
    
    printf("Generating %i random numbers modulo %i\n", N, modulo);
    nums = (int*) malloc(sizeof(int)*N);
    for(i=0; i<N; i++)
        nums[i] = rand() % modulo;
    
    // Print out the randomly generated sequence
    for(i=0; i<N; i++)
        printf(" %i ", nums[i]);
    printf("\n");
            
    printf("Option: (f)ind number or (q)uit?");
    scanf(" %c", &option);
    while (option != 'q') {
        printf("Value to look for? ");
        scanf(" %i", &key);
        
        result = linearSearch(nums,key,N);
        if (result != -1)
           printf("Found %d at position %d\n", key, result);
        else
           printf("Key %d not found\n", key);
       
        printf("Option: (f)ind number or (q)uit?");
        scanf(" %c", &option);
  }
}

    Once again, the linear search algorithm is the same one that you have seen before. But this time it has been modified using compiler directives.

    • Look at the piece of code in the search function that is surrounded by #ifdef TICKS and #endif. If you compile the program normally then the code sandwiched in between tick(a[i]) will be ignored. Why? Because TICKS is not defined. The program will behave exactly like linearsearch2. However...
    • If you were to compile the program like this: 
          gcc linearsearch3.c -DTICKS -o linearsearch3
      This would tell the compiler that TICKS is defined and the code sandwiched between #ifdef TICKS and #endif would be compiled into the program. You will see that this is a call to a function that we placed at the top of the file. Notice how it too is surrounded by #ifdef TICKS / #endif
    • The point of all this is that you have code which is conditionally compiled depending upon whether the relevant flag is defined or not. If the flag is defined then the program will print out a trace of all the values visited by the search algorithm when looking for the value you select. This trace will give you an idea of how the search algorithm is working and will give you an idea of how long it takes (i.e. by measuring the length of the output!).

    Compile and run the program. Try out different sizes of array.