Lab 13B: Binary Search

Objectives:

In this lab, we will practice:

Binary search

Background

Binary search is an algorithm that is much more efficient than linear search (for sorted arrays). It iteratively cuts in half the range of possible indices where a query may be.
For example, given the following array of numbers:

Assignment:

Develop algorithms to perform binary search. Extend your previous lab, and implement your algorithm in a separate function. Add a counter to your linear search function for the number of iterations required for the search. Additionally, add a similar counter to your binary search function. Furthermore, change your array to handle 10,000 elements. Prompt the user for 10,000 values and then prompt the user for a query. Perform linear search. Sort the numbers, but remove the code to display the numbers in sorted order. Perform binary search. Not the difference between the number of iterations for linear search and binary search.

Examples

Building off of the example from the previous lab, typing the following on the command-line:

./lab13B  <  /nfshome/hcarroll/public_html/2170/private/closedLabs/lab13B-stdin10000_407018.txt

your program should match lab13B-answerKey10000_407018.txt exactly (portions of the output are shown below)

Please enter 10000 numbers: 
You entered:
236603
976189
...
368909

Please enter a number to search for: 
You entered 407018
Linear search used 1966 iterations
407018 is located at index 1965

Binary search used 12 iterations
407018 is located at index 4135

Additionally, typing the following on the command-line:

./lab13B  <  /nfshome/hcarroll/public_html/2170/private/closedLabs/lab13B-stdin10000_741110.txt

your program should match lab13B-answerKey10000_741110.txt exactly (portions of the output are shown below)

Please enter 10000 numbers: 
You entered:
236603
976189
...
368909

Please enter a number to search for: 
You entered 741110
Linear search used 10000 iterations
741110 was not found

Binary search used 14 iterations
741110 was not found

Notice the large difference in the number of iterations between linear and binary search.
Note: When choosing the middle index of a range of an even number of indices, choose the higher middle value. For example, if there's 10,000 indices in the range, then choose index 5,000 for the middle index.

Submission

Submit your source code using the handin program. For handin, for this lab, type the following in a terminal window exactly as it appears:

handin  lab13B  main.cpp

To verify your submission, type the following in a terminal window:

handin  lab13B

Rubric:

Points  Item
------  --------------------------------------------------------------
10      Documentation
        Header comment block at the beginning of each file with:
        + Your full name
        + Date(s) code was written
        + Description
        Comments explaining the role of each variable and major section of code

40      Correctness
        Program solves the assigned problem using methods described in program description
	+ Prompts the user for 10 numbers
        + Stores those numbers in an array
        + Performs linear search
        + Sorts the numbers in ascending order
        Program compiles without errors
        Program executes without crashing
        Program produces the correct output
------  --------------------------------------------------------------
50      Total

CSCI 2170