Lab 9 – Searching

Implement Searching algorithms

What you will learn

• How to implement sequential search algorithms iteratively, and using recursion on arrays

• How to implement binary search algorithms iteratively, and using recursion on arrays

• How to implement sequential search algorithm on a linked list

The main file

The user interface for your searching algorithms is provided in a file called main.cpp. The user selects what searching algorithm needs to be run and on what data structure. Your task in this lab is to be able to implement the searching algorithms. The data structures required for this assignment are arrays, sorted arrays, and linked lists. You may use arrays and linked lists from your previous assignments or use the solution to labs 3 and 4 that will be released on 11/06.

Searching algorithms on unsorted arrays

Implement sequential search on the arrayList data structure from Lab 3 as a member function called unsigned int seqSearchIter (elemType element) and unsigned int seqSearchRec (elemType element) that returns the index at which the element is present using iteration and recursion respectively.

Searching algorithms on sorted arrays

Create a new template called sortedarrayList in a file called sortedarrayList.h with the functionalities as follows:

Implement binary search on the sortedarrayList data structure as a member function called unsigned int binarySearchIter (elemType element) and unsigned int binarySearchRec (elemType element) that returns the index at which the element is present using iteration and recursion respectively.

Searching algorithms on linked lists

Implement sequential search on the linkedListList data structure from Lab 4 as a member function called bool seqSearchIter (elemType element) and bool seqSearchRec (elemType element) that returns true if the element is present in the array and false otherwise, using iteration and recursion respectively.

What to turn in

A zip file containing arrayList.h, sortedarrayList.h, linkedListList.h, and main.cpp. Your zip file should be named Searching_XXXYYYXXX.zip, where XXXYYYXXX is your SJSU ID. E.g., if your SJSU ID is 111000111, your submission will be called Searching_111000111.zip.