Deliverables

Open the following in separate terminals for marking:

 

Back to Schedule

Lab Content

Quick Links

 

  • Preparation
  • Selection Sort
  • Compare Searching Algorithms

You can store your work for this part in the Searching directory.

You have been given the code for performing a Binary Search and the code for performing a Sequential Search. If you need them again, you can copy them now:

Binary Search

cp /net/data/ftp/pub/class/170/ftp/cpp/BinarySearch/BinSearch.h BinSearch.h
cp /net/data/ftp/pub/class/170/ftp/cpp/BinarySearch/BinSearch.cpp BinSearch.cpp
cp /net/data/ftp/pub/class/170/ftp/cpp/BinarySearch/BinMain.cpp BinMain.cpp

Sequential Search

cp /net/data/ftp/pub/class/170/ftp/cpp/BinarySearch/SeqSearch.h SeqSearch.h
cp /net/data/ftp/pub/class/170/ftp/cpp/BinarySearch/SeqSearch.cpp SeqSearch.cpp
cp /net/data/ftp/pub/class/170/ftp/cpp/BinarySearch/SeqMain.cpp SeqMain.cpp

Step 1-Modify the Binary Search

To get a better understanding of how the Binary Search is working, add some statements to the routine. i.e. Make these changes in BinSearch.cpp

  • Create a local variable in the BinarySearch function called "LoopCtr" and initialize it to 1.
  • After the
    Difference = IntArray[Mid] - Target; statement, add some cout statements to print the values of
    Target:   Mid:  Difference:  LoopCtr:  
  • After your new cout statements, add these statements:
    PrintArray(IntArray, Mid);
    LoopCtr++;

Step 2-Compare the Runs

Run the code and search for the first, middle, and last items. Based on your observations, construct the following table in a file and save it to show your lab instructor:

  Sequential Binary
Is the data sorted? (yes or no)    
How many comparisons are made to find the first item (index 0)?    
How many comparisons are made to find the middle item (index 49)?    
How many comparisons are made to find the last item (index 99)?    

Step 3-Challenge Questions

Save these questions and your answers to the same file as above.

Suppose your array contained 1,000,000 elements:

  1. For a Sequential Search, how many comparisons would the program need to find the last value in the array?

  2. For a Binary Search, how many comparisons would the program need to find the last value?  

  3. In this case, which do you think will be faster?