Lesson 26 lab exercise 1 - search -  

Background:

You will need to have completed the store.cpp program from Lesson 25.  You may either type in the following testing function or your instructor will supply this short piece of code on disk.  Your task will be to complete the stubbed-out binary search algorithm.

void testSearch (const storeType &store)

{

        int idToFind, invReturn, index;

        cout << "Testing search algorithm" << endl << endl;

        cout << "Enter Id value to search for (-1 to quit) ---> ";

        cin >> idToFind;

        while (idToFind >= 0)

        {

                index = bsearch (store, idToFind);

        //     index = bsearch (store, idToFind, 0, store.number-1);    recursive version call

                cout << "Id # " << idToFind;

                if (-1 == index)

                        cout << "     No such part in stock" << endl;

                else

                        cout << "     Inventory = " << store.list[index].inv << endl;

                cout << endl << "Enter Id value to search for (-1 to quit) ---> ";

                cin >> idToFind;

        }

}

int bsearch (const storeType &store, int idToSearch)

/*    precondition:  store.list is sorted by the id field.  store.number stores how many items are in the array.

        data is stored in the array list from positions 0..store.number-1.

        postcondition:  if idToSearch exists in the array, the function returns the index position of the item, otherwise it returns -1.  */

{

        return -1;

}

int bsearch (const storeType &store, int idToSearch, int first, int last)

//     recursive version, searches range from first to last of the array

Assignment:

1.   Add the above code to your store.cpp code.  Change the name of your program to search.cpp.  Complete the binary search algorithm and test your solution with sample test id values as supplied by your instructor.

2.   Depending on the directions of your instructor, test either or both the non-recursive and recursive binary search solution(s).

Instructions:

1.   Turn in the completed source code for only the binary search function and a printed run output.  The run output should consist only of the appropriate answers.  An example is given below.

Id # 15320     Inventory = 82

Id # 196     Inventory = 60

Id # 19967     Inventory = 45

Id # 2   No such part in stock

Id # 20000   No such part in stock