I just need help with Searching.h please do not change the code

Searching.h

#ifndef SEARCHING_H_ #define SEARCHING_H_

#include "Vector.h" #include "List.h" using namespace std;

template void print_vector(const Vector& vec) { for (int i = 0; i

// LINEAR SEARCH OF VECTOR // return index at which target found, if not found return -1; template int linear_search_V(const Vector& vec, const T& target, int& ops) { ops = 0; for(int i=0;i

// LINEAR SEARCH OF LINKED LIST // return iterator to node at which target // found in lst; else return iterator at end() of lst;

template typename List::const_iterator linear_search_L(const List& lst, const T& target, int& ops) { ops = 0; typename List::const_iterator itr; for (itr=lst.begin(); itr != lst.end(); ++itr) { ops++; if (*itr++ == target) return itr; } return lst.end(); }

// BINARY SEARCH OF VECTOR; // returns index at which target found, else -1;

template int binary_search_V(const Vector& vec, const T& target, int& ops) { ops = 0; int low=0; int high = vec.size() -1; while(low target) high = mid -1; else return mid; } return -1; }

// BINARY SEARCH OF LINKED LIST // returns iterator at target value found; iterator end() else;

template typename List::const_iterator binary_search_L(const List lst, const T& target, int& ops) { ops = 0;

// HW: Implement this function; }

#endif

List.h

#ifndef LIST_H #define LIST_H

using namespace std;

template class List { private: struct Node { T data; Node *prev; Node *next;

Node( const T & d = T{ }, Node * p = nullptr, Node * n = nullptr ) : data{ d }, prev{ p }, next{ n } { } Node( T && d, Node * p = nullptr, Node * n = nullptr ) : data{ std::move( d ) }, prev{ p }, next{ n } { } };

public: class const_iterator { public: // Public constructor for const_iterator. const_iterator( ) : current{ nullptr } { } const T & operator* ( ) const { return retrieve( ); } const_iterator & operator++ ( ) { current = current->next; return *this; }

const_iterator operator++ ( int ) { const_iterator old = *this; ++( *this ); return old; }

const_iterator & operator-- ( ) { current = current->prev; return *this; }

const_iterator operator-- ( int ) { const_iterator old = *this; --( *this ); return old; } bool operator== ( const const_iterator & rhs ) const { return current == rhs.current; }

bool operator!= ( const const_iterator & rhs ) const { return !( *this == rhs ); }

// iterators side-by-side bool operator > (const const_iterator & rhs) const { return current->prev == rhs.current; }

protected: Node *current; T & retrieve( ) const { return current->data; } const_iterator( Node *p ) : current{ p } { } friend class List; };

class iterator : public const_iterator { public: iterator( ) { }

T & operator* ( ) { return const_iterator::retrieve( ); }

const T & operator* ( ) const { return const_iterator::operator*( ); } iterator & operator++ ( ) { this->current = this->current->next; return *this; }

iterator operator++ ( int ) { iterator old = *this; ++( *this ); return old; }

iterator & operator-- ( ) { this->current = this->current->prev; return *this; }

iterator operator-- ( int ) { iterator old = *this; --( *this ); return old; }

protected: iterator( Node *p ) : const_iterator{ p } { }

friend class List; };

public: List( ) { init( ); }

~List( ) { clear( ); delete head; delete tail; }

List( const List & rhs ) { init( ); for( auto & x : rhs ) push_back( x ); }

List & operator= ( const List & rhs ) { List copy = rhs; std::swap( *this, copy ); return *this; }

// keep for compiler List(List&& rhs) : theSize{ rhs.theSize }, head{ rhs.head }, tail{ rhs.tail } { rhs.theSize = 0; rhs.head = nullptr; rhs.tail = nullptr; } // keep for compiler List& operator= (List&& rhs) { std::swap(theSize, rhs.theSize); std::swap(head, rhs.head); std::swap(tail, rhs.tail);

return *this; } iterator begin( ) { return iterator( head->next ); }

const_iterator begin( ) const { return const_iterator( head->next ); } iterator end( ) { return iterator( tail ); }

const_iterator end( ) const { return const_iterator( tail ); }

// Return number of elements currently in the list. int size( ) const { return theSize; }

// Return true if the list is empty, false otherwise. bool empty( ) const { return size( ) == 0; }

void clear( ) { while( !empty( ) ) pop_front( ); } T & front( ) { return *begin( ); }

const T & front( ) const { return *begin( ); }

T & back( ) { return *--end( ); }

const T & back( ) const { return *--end( ); }

void push_front( const T & x ) { insert( begin( ), x ); }

void push_back( const T & x ) { insert( end( ), x ); }

void pop_front( ) { erase( begin( ) ); }

void pop_back( ) { erase( --end( ) ); }

// Insert x before itr. iterator insert( iterator itr, const T & x ) { Node *p = itr.current; ++theSize; return iterator( p->prev = p->prev->next = new Node{ x, p->prev, p } ); } // Erase item at itr. iterator erase( iterator itr ) { Node *p = itr.current; iterator retVal( p->next ); p->prev->next = p->next; p->next->prev = p->prev; delete p; --theSize;

return retVal; }

iterator erase( iterator from, iterator to ) { for( iterator itr = from; itr != to; ) itr = erase( itr );

return to; }

private: int theSize; Node *head; Node *tail;

void init( ) { theSize = 0; head = new Node; tail = new Node; head->next = tail; tail->prev = head; } };

#endif

Main.cpp

In this assignment, you will conduct an empirical study on the computational performances of linear search and binary search on ADTS Vector and List. You may download and use the following files with complete code that do not need your modifications: . Vector.h List.h Random.h and Random.cpp HW3Main.cpp Also download the incomplete file Searching.h Then download - HW3_Stats, and Excel spreadsheet (.pdf also provided) Task 1: (10 pts) Complete the functions in file Searching.h as indicated. For three out of the four function, the lecture material will provide much. For the fourth function, binary search of a linked list, you are asked to think about an algorithm to accomplish this task and to render your algorithm in C++ code. Like linear search of a list, binary search of a list is to return the iterator to the item found or the list's end() iterator. Hint: Binary search always determines the approximate) middle of a linear structure, compares the target to the middle value, and if needed, proceeds with searching either the left or right half. There are no random access operators (int) for linked lists. Nevertheless, it is possible to determine and access the middle element of a list, and proceed with focus on only the left or right half of the list. Figure out to do this, and you will be able to implement binary search for linked list. In order to record the computational cost of binary search of fists, increase the reference argument int& ops each time a list iterator is moved. Run the provided int main() in HW3Main.cpp. It will output performance data for all four search functions on sorted data collections of sizes 50, 100, 150,..... 250. Random numbers will range from 1 to 10000. Each search function will run for 10 random targets for each data collection size. #include #include #include "Vector.h" #include "List.h" #include "Random.h" #include "Searching.h" using namespace std; int main() { rand_seed(); for (int k = 50; k myvec; random_vector_norep (k, 1, 10000, myvec, 0); Vector sortvec (myvec); sort (sortvec.begin(), sortvec.end()); List sortlist; for (int i = 0; i targets; random_vector_norep (10, 0, myvec.size() - l, targets 0); int opsl = 0; int op 32 = 0; int op s3 = 0; int op 34 = 0; for (int i = 0; i #include #include "Vector.h" #include "List.h" #include "Random.h" #include "Searching.h" using namespace std; int main() { rand_seed(); for (int k = 50; k myvec; random_vector_norep (k, 1, 10000, myvec, 0); Vector sortvec (myvec); sort (sortvec.begin(), sortvec.end()); List sortlist; for (int i = 0; i targets; random_vector_norep (10, 0, myvec.size() - l, targets 0); int opsl = 0; int op 32 = 0; int op s3 = 0; int op 34 = 0; for (int i = 0; i