Question: how can i implement a binary search of a linked list to make my main.cpp work? i have 4 functions a linear search of vector,
how can i implement a binary search of a linked list to make my main.cpp work? i have 4 functions a linear search of vector, a linear search of linked List, a Binary search of a vector the one i need help is the binary search of a linked List(Part in Bold Letters). can you please complete the function. Use iterators.
Searching.h
#ifndef SEARCHING_H_
#define SEARCHING_H_
#include "Vector.h"
#include "List.h"
using namespace std;
template
void print_vector(const Vector
{
for (int i = 0; i
cout
cout
return;
}
// LINEAR SEARCH OF VECTOR
// return index at which target found, if not found return -1;
template
int linear_search_V(const Vector
{
ops = 0;
for(int i=0;i
{
ops++;
if (vec[i] == target)
return i;
}
return -1;
}
// 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
{
ops = 0;
typename List
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
{
ops = 0;
int low=0;
int high = vec.size() -1;
while(low
{
ops++;
int mid =(low+high)/2;
if (vec[mid] low= mid +1; else if (vec[mid] > 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 { ops = 0; implement function for binary search in Linked List: } #endif Here is the List.h if needed List.h #ifndef LIST_H #define LIST_H //#include using namespace std; template class List { private: // The basic doubly linked list node. // Nested inside of List, can be public // because the Node is itself 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 } { } // Return the T stored at the current position. // For const_iterator, this is an accessor with a // const reference return type. 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; // Protected helper in const_iterator that returns the T // stored at the current position. Can be called by all // three versions of operator* without any type conversions. T & retrieve( ) const { return current->data; } // Protected constructor for const_iterator. // Expects a pointer that represents the current position. const_iterator( Node *p ) : current{ p } { } friend class List }; class iterator : public const_iterator { public: // Public constructor for iterator. // Calls the base-class constructor. // Must be provided because the private constructor // is written; otherwise zero-parameter constructor // would be disabled. 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: // Protected constructor for iterator. // Expects the current position. 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; } // Return iterator representing beginning of list. // Mutator version is first, then accessor version. iterator begin( ) { return iterator( head->next ); } const_iterator begin( ) const { return const_iterator( head->next ); } // Return iterator representing endmarker of list. // Mutator version is first, then accessor version. 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( ); } // front, back, push_front, push_back, pop_front, and pop_back // are the basic double-ended queue operations. 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 and the Main.cpp 
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help