This is an assignment for a class, for this program i need to implement a binary search for linked List, how can i do that? is it 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? how can i implement binary search for linked list?
Searching.h
#ifndef SEARCHING_H_
#define SEARCHING_H_
#include "Vector.h"
#include "List.h"
using namespace std;
template <typename T>
void print_vector(const Vector<T>& vec)
{
for (int i = 0; i < vec.size(); i++)
cout << vec[i] << " ";
cout << endl;
return;
}
// LINEAR SEARCH OF VECTOR
// return index at which target found, if not found return -1;
template <typename T>
int linear_search_V(const Vector<T>& vec, const T& target, int& ops)
{
ops = 0;
for (int i = 0; i < vec.size(); 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 T>
typename List<T>::const_iterator linear_search_L(const List<T>& lst, const T& target, int& ops)
{
ops = 0;
typename List<T>::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 <typename T>
int binary_search_V(const Vector<T>& vec, const T& target, int& ops)
{
ops = 0;
int low = 0;
int high = vec.size() - 1;
while (low <= high) {
ops++;
int mid = (low + high) / 2;
if (vec[mid] < target)
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 T>
typename List<T>::const_iterator binary_search_L(const List<T> lst, const T& target, int& ops)
{
ops = 0;
//implement function for binary search in Linked List:
}
#endif
//this is the List.h i need to use for the binary search in a linked list
#ifndef LIST_H
#define LIST_H
//#include <algorithm>
using namespace std;
template <typename T>
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<T>;
};
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<T>;
};
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
A binary search on a linked list is an odd concept, but let's hold off on the oddity for the moment. To start, let's adapt the binary search algorithm to the linked list interface.
To start a binary search, you need the middle of the list. So first you need to know how long your list is. If the list had not stored its size, the size could be determined by iterating over the list, counting nodes as you proceed. Once you have the size, you divide by 2 as normal. Also, cache a copy of the pointer to the head of the list, for a reason that will become clear later.
Once you know which node you need, you start with your cached head pointer and advance that many nodes. If you found the desired node, you are done. If the middle node is too low, replace your cached head pointer with a pointer to the midpoint node (which has become the new low end of your search). In either case (too low or too high), divide the index of the node you had looked for by two and repeat.
Note: the code for this might very well look complicated and/or messy, especially when compared to the vector version.
Well, the above also needs a check to for "not found". There is probably also some round-off error to deal with. While these are important, I'd rather look at why one might want to do this. (Besides, working on those details might be useful practice. You still have to do some work for your assignment. ;) )
How effective is this binary search compared to a linear search for a list of length n? A linear search will, on average compare n/2 nodes and follow n/2 links. A binary search, on the other hand, will on average compare lg n nodes and follow n links (or something more like n lg n links if you do not cache the starting point). Perhaps more striking is that a binary search will at minimum follow n/2 links (to get to the first midpoint), which is average for a binary search. How could a binary search hope to ever be better than linear?
One possibility lies in the number of comparisons. If comparing nodes is particularly expensive, the reduced number of comparisons could (in theory) make up for the increased amount of walking through the list. I don't know any examples of when this comes into play, but I'll grant the possibility. Theoretically.
What I find more likely is that you were given this assignment to drive home the point that you do not want to do a binary search on a linked list. Drive home the idea that if you need to do a binary search, you'll want a container (like a vector) that provides random access to its elements. Use the right tool for the job at hand.