Question
Please Help!. i need to implement a binary search in a linked list and returns iterator at target value found. how can i do that
Please Help!. i need to implement a binary search in a linked list and returns iterator at target value found. how can i do that in this file code?
i have a 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 lists, increase the reference argument int& ops each time a list iterator is moved.
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 here: } #endif this is my 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 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 this is my main.cpp in case you need it 
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
Machine Learning And Knowledge Discovery In Databases European Conference Ecml Pkdd 2019 Wurzburg Germany September 16 20 2019 Proceedings Part 2 Lnai 11907
Authors: Ulf Brefeld ,Elisa Fromont ,Andreas Hotho ,Arno Knobbe ,Marloes Maathuis ,Celine Robardet
1st Edition
