我如何在链接列表中创建二进制搜索？
how can i create a binary search in a linked List?
这是一个 class 的作业，对于这个程序，我需要对链表执行二进制搜索，我该怎么做？是否可以确定和访问列表的中间元素，然后只关注左侧或
列表的右半部分？
我如何实现链表的二进制搜索？
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
在链表上使用二分查找是没有意义的，因为随机访问在链表中具有高得令人望而却步的time complexity。在单向链表中，平均而言，每次随机访问都必须遍历链表的一半。这与执行整个搜索的简单线性搜索平均所需的工作量相同。
与其将节点排列在链表中，其中每个节点最多与另一个节点链接，不如将节点排列在树中，其中每个节点最多与另外两个节点链接.我建议将它们排列成 binary search tree，因为这是二进制搜索的理想数据结构。
链表上的二分查找是一个奇怪的概念，但让我们暂时搁置这个奇怪的话题。首先，让我们将二分查找算法应用于链表接口。
要开始二进制搜索，您需要列表的中间位置。所以首先你需要知道你的清单有多长。如果列表未存储其大小，则可以通过遍历列表并在继续时对节点进行计数来确定大小。一旦你有了大小，你就可以像往常一样除以 2。此外，缓存指向列表头部的指针的副本，原因稍后会变得清楚。
一旦您知道您需要哪个节点，您就可以从缓存的头指针开始并推进那么多节点。如果您找到了所需的节点，那么您就完成了。如果中间节点太低，请将缓存的头指针替换为指向中点节点（已成为搜索的新低端）的指针。在任何一种情况下（太低或太高），将您查找的节点的索引除以二并重复。
注意：此代码可能看起来很复杂 and/or 凌乱，尤其是与矢量版本相比时。
嗯，以上还需要检查“未找到”。可能还需要处理一些舍入误差。虽然这些很重要，但我宁愿看看为什么有人可能想要这样做。 （此外，处理这些细节可能是有用的练习。您仍然需要为作业做一些工作。;））
与长度为 n 的列表的线性搜索相比，此二分搜索的效果如何？线性搜索平均会比较 n/2 个节点并跟踪 n/2 个链接。另一方面，二进制搜索将平均比较 lg n 个节点并遵循 n 个链接（如果不缓存起点，则更像是 n lg n 个链接）。也许更引人注目的是二分搜索将 至少 遵循 n/2 链接（到达第一个中点），即 平均 用于二进制搜索。二分搜索怎么可能比线性搜索更好？
一种可能是比较次数。如果比较节点的成本特别高，则比较次数的减少（理论上）可以弥补遍历列表的增加量。我不知道这何时起作用的任何例子，但我会承认这种可能性。理论上。
我发现更有可能的是，你被赋予这项任务是为了让你知道你不想想在链表上进行二进制搜索。深入了解如果您需要进行二进制搜索，您将需要一个容器（如向量）来提供对其元素的随机访问。为手头的工作使用正确的工具。
这是一个 class 的作业，对于这个程序，我需要对链表执行二进制搜索，我该怎么做？是否可以确定和访问列表的中间元素，然后只关注左侧或 列表的右半部分？ 我如何实现链表的二进制搜索？
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
在链表上使用二分查找是没有意义的，因为随机访问在链表中具有高得令人望而却步的time complexity。在单向链表中，平均而言，每次随机访问都必须遍历链表的一半。这与执行整个搜索的简单线性搜索平均所需的工作量相同。
与其将节点排列在链表中，其中每个节点最多与另一个节点链接，不如将节点排列在树中，其中每个节点最多与另外两个节点链接.我建议将它们排列成 binary search tree，因为这是二进制搜索的理想数据结构。
链表上的二分查找是一个奇怪的概念，但让我们暂时搁置这个奇怪的话题。首先，让我们将二分查找算法应用于链表接口。
要开始二进制搜索，您需要列表的中间位置。所以首先你需要知道你的清单有多长。如果列表未存储其大小，则可以通过遍历列表并在继续时对节点进行计数来确定大小。一旦你有了大小，你就可以像往常一样除以 2。此外，缓存指向列表头部的指针的副本，原因稍后会变得清楚。
一旦您知道您需要哪个节点，您就可以从缓存的头指针开始并推进那么多节点。如果您找到了所需的节点，那么您就完成了。如果中间节点太低，请将缓存的头指针替换为指向中点节点（已成为搜索的新低端）的指针。在任何一种情况下（太低或太高），将您查找的节点的索引除以二并重复。
注意：此代码可能看起来很复杂 and/or 凌乱，尤其是与矢量版本相比时。
嗯，以上还需要检查“未找到”。可能还需要处理一些舍入误差。虽然这些很重要，但我宁愿看看为什么有人可能想要这样做。 （此外，处理这些细节可能是有用的练习。您仍然需要为作业做一些工作。;））
与长度为 n 的列表的线性搜索相比，此二分搜索的效果如何？线性搜索平均会比较 n/2 个节点并跟踪 n/2 个链接。另一方面，二进制搜索将平均比较 lg n 个节点并遵循 n 个链接（如果不缓存起点，则更像是 n lg n 个链接）。也许更引人注目的是二分搜索将 至少 遵循 n/2 链接（到达第一个中点），即 平均 用于二进制搜索。二分搜索怎么可能比线性搜索更好？
一种可能是比较次数。如果比较节点的成本特别高，则比较次数的减少（理论上）可以弥补遍历列表的增加量。我不知道这何时起作用的任何例子，但我会承认这种可能性。理论上。
我发现更有可能的是，你被赋予这项任务是为了让你知道你不想想在链表上进行二进制搜索。深入了解如果您需要进行二进制搜索，您将需要一个容器（如向量）来提供对其元素的随机访问。为手头的工作使用正确的工具。