- 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

statement, add some cout statements to print the values of*Difference = IntArray[Mid] - Target;*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:

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

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

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