查找算法详解

定义：根据给定的某一个值，在查找表中确定一个关键字等于给定的值的数据元素

查找算法的分类：动态查找和静态查找；无序查找和有序查找；无序查找和有序查找

平均查找的长度：ASL:需要和指定的key进行比较的关键字的个数的期望值。对于n个数据元素的查找表，查找成功的平均查找长度位：ASL = PI*CI 。PI时查找到第i个数据元素的概率。CI：找到第i个元素时已经比较过得出次数

顺序查找

算法思想

从线性表的一端开始，顺序查找，直到找到指定的代码为止

代码实现

for(int i = 0 ; i < listlength ;i++ ){
if(list[i] == key)return i;
}

进行优化

//在头部插入哨兵，依次从后往前进行比较，可以免去每一步都要检查是不是越界
list[0].key = key; //设置哨兵
for(int i = listlength ; list[i].key != key ; i--)
return i;

算法分析

平均查找长度 ASL = (N+1)/2;

查找不成功时需要n+1次比较所以，时间复杂度时O(n)

分块查找

基本思想

分块查找（Blocking Search）又称索引顺序查找，这是一种性能介于顺序查找和折半查找之间的一种查找方法。

分块查找中，需要建立一个“索引表”来划分块区域，通过定位某一块区域来查找相应信息；
索引表包括两项内容：最大关键项、最大关键项块区域的指针项；
对索引表来说是有序的顺序表，可用顺序查找和折半查找两种方法查找索引表；
而对索引表所标识的块区域中的数据是无序的，所以只能使用顺序查找。

代码实现

int low = L;
int high = R;
int mid = (low+high)/2;
while(low < high)
//先折半查找索引表
{
if(key == I[mid].maxkey)
break;
else
{
if(key < I[mid].maxkey) //缩小查找范围到左子序列
high = mid;
else
//缩小查找范围到右子序列
low = mid +1;
}
mid = (low+high)/2;
}
int i, end, start = I[mid].address;	//找key值所在的区间首地址
if(mid == R)	//确定查找的结束地址
end = len + 1;
else
end = I[mid+1].address;
for(i = start; i < end; i++)//再顺序查找该区间
if(key == K[i].key)
return i;
//返回位置
return 0;
}

算法分析

O(log2n)~O(n)之间

二分查找

基本思想

首先元素时有序的，如果你要时没有顺序，那么对不起，先进行排序

二分查找又叫折半查找，就是把给定的值key和中间的节点进行比较，然后把线性表分成了两个子表，然后不断的进行继续分。

代码

//递归版本的代码
int search1(int a[],int key,int left,int right)
{
int mid = (left + right)/2;
if(left > right)return -1;
if(a[mid] == key)return mid;
if(a[mid] < key)return search1(a[],key,mid+1,right);
if(a[mid] > key)return search1(a[],key,left,mid-1);
}
//非递归版本的代码
int search2(int a[],int key,int length)
{
int left,right,mid;
left = 0;right = length - 1;
while(left <= right)
{
mid = (left + right) / 2;
if(a[mid] == key)return mid;
if(a[mid] > key)right = mid -1;
if(a[mid] < key)left = mid + 1;
}
}

算法分析

折半查找的运行过程可以使用二叉树来进行表示，这一棵树通常被称为“判定树”

对于具有n个节点的判定树，他的层次至多为 $lo{g}_{2}n$ + 1 结果如果不是整数向下取整

ASL=$lo{g}_2(n+1)$ - 1

最坏的情况下关键此比较的次数是$lo{g}_2(n+1)$ 所以时间复杂度树O($lo{g}_{2}n$)

插值查找

算法思想

基于二分查找算法，将查找点的选择改为自适应选择，可以提高查找效率，由于是二分查找的变异，所以插值查找属于有序查找

你仔细想一想，有必要一定选择二分查找吗？不一定把，你可以选择四分之一处吧，也可以选着三分之一处吧。所以说，折半查找不具有自适应性，这也就意味着有可能会有比他效率更搞的折半。

二分查找的计算

mid = (left + right) / 2 ，也就是 mid = low + 1/2 * （left - right）

我们改进一下

mid = left + (key - a[left]) /(a[right] - a[left]) * (right - left)

我们仅仅进行了系数1/2的改变，我们把1/2改进成了自适应的参数，这样跟关键字在有序表中的位置，让mid的值的变化更加接近关键字，这样也就简介减少了比较的次数

有一说一：当你表长大，而且关键字分布比较均匀的查找表来说，确实很好用，到那时如果分布很少不均匀，使用插值并不是一个好选择

代码

int left = 0 ,mid ,right = listlength -1;
while(left <= right)
{
mid = left + (key - list[left])/(list[right] - list[left]);
if(key < list[mid])
{
right = mid - 1;
}
else if(key > list[mid])
{
left = mid + 1;
}
else
{
return mid;
}
}

算法分析

查找成功或者失败的时间复杂度O($lo{g}_2(lo{g}_{2}n)$)

斐波那契查找

基本思想

还是二分查找的一种提升算法，通过利用黄金比例在数列中选择查找点进行查找，来提高查找效率。那么这也是一种有序查找算法

要求开始表中记录的个数为某个斐波那契数小1，及n = F(k) - 1;

开始将key值和第F(k-1)位置的记录进行比较（也就是：mid = left + F（k-1）- 1）比较结果也分为三种

1：相等，那么return mid

2; key > mid , left = mid + 1,k-=2;

解释：low = mid + 1 上面查找的元素在【mid + 1 ，right 】范围内，k-=2说明分为在[mid+1 ， right]内的个数为n - (F(k-1)) =

F(k) - 1 - F(k-1) = F(k) - F(k-1)-1 = F(k-2) -1 个，所以可以使用递归应用斐波那契查找

3 key < mid , right = mid - 1 , k-=1;

解释： low = mid + 1 说明待查找的元素在[left, mid -1]内， k-= 1 说明非为[left , mid-1]内的元素个数为F(k-1) - 1个，所以可以递归的应用斐波那契数列

代码

void fib(int *f)
{
f[0],f[1] = 1;
for(int i = 2; i < 20; i++)//20仅仅是一个暂定的数字可以修改
{
f[i] f[i-2] + f[i - 1];
}
}
int fibsearch(int *a, int key, int length)
{
int i,left = 0,right = length - 1;
int mid = 0;
int k = 0;
int F[20];//20仅仅是一个暂定的数字可以修改
fib(F);
while(n > F[k] - 1)//计算处n在斐波那契中的数列
k++;
for(i = length ; i < F[k - 1] ;i++)
a[i] = a[right];//补全数组
while(left <= right)
{
mid = left + F[k - 1] - 1 ;//根据斐波那契数列进行黄金分割
if(a[mid] > key){
right = mid - 1;
k = k -1;
}
else if(a[mid] < key )
{
left = mid = 1;
k-= 2;
}
else
{
if(mid <= right)return mid;
else return -1;
}
}
return 0;
}

算法分析

最坏的情况下，时间复杂度O($lo{g}_{2}n$)，所以复杂度也是O($lo{g}_{2}n$)。

树表查找

二叉树查找

我家门前有两棵树，一棵是二叉树，另一棵也是二叉树

基本思想

首先先生成一棵二叉排序树，然后根据左分支一定大于右分支的原则不断的进行查找

代码

while(root != nullptr)
{
if(root->data == key)return root;
else if(root->data > key)root = root->lchild;
else root = root->rchild;
}

算法分析

在正常的情况下，应该是O($lo{g}_{2}n$)，但是要是极端一点O(n)也是有可能的。所以需要优化，下面给出优化算法

平衡查找树之2-3查找树

2-3查找树定义：

2-节点：含有一个键和两条链接，左链接指向的2-3树中的键都小于该节点，右链接指向的2-3树中的键都大于该节点。

3-节点：含有两个键和三条链接，左链接指向的2-3树中的键都小于该节点，链接指向的2-3树中的键都位于该节点的两个键之间，右链接指向的2-3树中的键都大于该节点。

这样多了一个3节点之后，树就多了分配节点的能力

具体文章请参考

代码

public class Tree234 {
private Node root = new Node() ;
/*public Tree234(){
root = new Node();
}*/
//查找关键字值
public int find(long key){
Node curNode = root;
int childNumber ;
while(true){
if((childNumber = curNode.findItem(key))!=-1){
return childNumber;
}else if(curNode.isLeaf()){//节点是叶节点
return -1;
}else{
curNode = getNextChild(curNode,key);
}
}
}
public Node getNextChild(Node theNode,long theValue){
int j;
int numItems = theNode.getNumItems();
for(j = 0 ; j < numItems ; j++){
if(theValue < theNode.getItem(j).dData){
return theNode.getChild(j);
}
}
return theNode.getChild(j);
}
//插入数据项
public void insert(long dValue){
Node curNode = root;
DataItem tempItem = new DataItem(dValue);
while(true){
if(curNode.isFull()){//如果节点满数据项了，则分裂节点
split(curNode);
curNode = curNode.getParent();
curNode = getNextChild(curNode, dValue);
}else if(curNode.isLeaf()){//当前节点是叶节点
break;
}else{
curNode = getNextChild(curNode, dValue);
}
}//end while
curNode.insertItem(tempItem);
}
public void split(Node thisNode){
DataItem itemB,itemC;
Node parent,child2,child3;
int itemIndex;
itemC = thisNode.removeItem();
itemB = thisNode.removeItem();
child2 = thisNode.disconnectChild(2);
child3 = thisNode.disconnectChild(3);
Node newRight = new Node();
if(thisNode == root){//如果当前节点是根节点，执行根分裂
root = new Node();
parent = root;
root.connectChild(0, thisNode);
}else{
parent = thisNode.getParent();
}
//处理父节点
itemIndex = parent.insertItem(itemB);
int n = parent.getNumItems();
for(int j = n-1; j > itemIndex ; j--){
Node temp = parent.disconnectChild(j);
parent.connectChild(j+1, temp);
}
parent.connectChild(itemIndex+1, newRight);
//处理新建的右节点
newRight.insertItem(itemC);
newRight.connectChild(0, child2);
newRight.connectChild(1, child3);
}
//打印树节点
public void displayTree(){
recDisplayTree(root,0,0);
}
private void recDisplayTree(Node thisNode,int level,int childNumber){
System.out.println("levle="+level+" child="+childNumber+" ");
thisNode.displayNode();
int numItems = thisNode.getNumItems();
for(int j = 0; j < numItems+1 ; j++){
Node nextNode = thisNode.getChild(j);
if(nextNode != null){
recDisplayTree(nextNode, level+1, j);
}else{
return;
}
}
}
//数据项
class DataItem{
public long dData;
public DataItem(long dData){
this.dData = dData;
}
public void displayItem(){
System.out.println("/"+dData);
}
}
//节点
class Node{
private static final int ORDER = 4;
private int numItems;//表示该节点有多少个数据项
private Node parent;//父节点
private Node childArray[] = new Node[ORDER];//存储子节点的数组，最多有4个子节点
private DataItem itemArray[] = new DataItem[ORDER-1];//存放数据项的数组，一个节点最多有三个数据项
//连接子节点
public void connectChild(int childNum,Node child){
childArray[childNum] = child;
if(child != null){
child.parent = this;
}
}
//断开与子节点的连接，并返回该子节点
public Node disconnectChild(int childNum){
Node tempNode = childArray[childNum];
childArray[childNum] = null;
return tempNode;
}
//得到节点的某个子节点
public Node getChild(int childNum){
return childArray[childNum];
}
//得到父节点
public Node getParent(){
return parent;
}
//判断是否是叶节点
public boolean isLeaf(){
return (childArray[0] == null)?true:false;
}
//得到节点数据项的个数
public int getNumItems(){
return numItems;
}
//得到节点的某个数据项
public DataItem getItem(int index){
return itemArray[index];
}
//判断节点的数据项是否满了（最多3个）
public boolean isFull(){
return (numItems == ORDER-1) ? true:false;
}
//找到数据项在节点中的位置
public int findItem(long key){
for(int j = 0 ; j < ORDER-1 ; j++){
if(itemArray[j]==null){
break;
}else if(itemArray[j].dData == key){
return j;
}
}
return -1;
}
//将数据项插入到节点
public int insertItem(DataItem newItem){
numItems++;
long newKey = newItem.dData;
for(int j = ORDER-2 ; j >= 0 ; j--){
if(itemArray[j] == null){//如果为空，继续向前循环
continue;
}else{
long itsKey = itemArray[j].dData;//保存节点某个位置的数据项
if(newKey < itsKey){//如果比新插入的数据项大
itemArray[j+1] = itemArray[j];//将大数据项向后移动一位
}else{
itemArray[j+1] = newItem;//如果比新插入的数据项小，则直接插入
return j+1;
}
}
}
//如果都为空，或者都比待插入的数据项大，则将待插入的数据项放在节点第一个位置
itemArray[0] = newItem;
return 0;
}
//移除节点的数据项
public DataItem removeItem(){
DataItem temp = itemArray[numItems-1];
itemArray[numItems-1] = null;
numItems--;
return temp;
}
//打印节点的所有数据项
public void displayNode(){
for(int j = 0 ; j < numItems ; j++){
itemArray[j].displayItem();
}
System.out.println("/");
}
}
}

复杂度分析

最坏的情况下，所有的节点都是2节点效率是O($lo{g}_{2}n$)

最好的情况下，所有的节点都是3节点，效率是O($lo{g}_{3}n$)

红黑树

基本定义

• *根节点是黑色的；*
• *每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数；*
• *任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；*
• *每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色*

更多细节

代码实现

//过于复杂，建议自行百度

算法分析

时间复杂度：最坏也是对数级

B-和B+树

基本思想：

对2-3树的一种扩展，根节点至少有两个节点，每个节点有M-1个key，并且可以升序排列；位于M-1和Mkey的子节点的值位于M-1和Mkey对应的value之间；其他节点至少有M/2个节点

代码实现

// C++ program for B-Tree insertion
#include<iostream>
using namespace std;
// A BTree node
class BTreeNode
{
int *keys;
// An array of keys
int t;
// Minimum degree (defines the range for number of keys)
BTreeNode **C; // An array of child pointers
int n;
// Current number of keys
bool leaf; // Is true when node is leaf. Otherwise false
public:
BTreeNode(int _t, bool _leaf);
// Constructor
// A utility function to insert a new key in the subtree rooted with
// this node. The assumption is, the node must be non-full when this
// function is called
void insertNonFull(int k);
// A utility function to split the child y of this node. i is index of y in
// child array C[].
The Child y must be full when this function is called
void splitChild(int i, BTreeNode *y);
// A function to traverse all nodes in a subtree rooted with this node
void traverse();
// A function to search a key in subtree rooted with this node.
BTreeNode *search(int k);
// returns NULL if k is not present.
// Make BTree friend of this so that we can access private members of this
// class in BTree functions
friend class BTree;
};
// A BTree
class BTree
{
BTreeNode *root; // Pointer to root node
int t;
// Minimum degree
public:
// Constructor (Initializes tree as empty)
BTree(int _t)
{
root = NULL;
t = _t; }
// function to traverse the tree
void traverse()
{
if (root != NULL) root->traverse(); }
// function to search a key in this tree
BTreeNode* search(int k)
{
return (root == NULL)? NULL : root->search(k); }
// The main function that inserts a new key in this B-Tree
void insert(int k);
};
// Constructor for BTreeNode class
BTreeNode::BTreeNode(int t1, bool leaf1)
{
// Copy the given minimum degree and leaf property
t = t1;
leaf = leaf1;
// Allocate memory for maximum number of possible keys
// and child pointers
keys = new int[2*t-1];
C = new BTreeNode *[2*t];
// Initialize the number of keys as 0
n = 0;
}
// Function to traverse all nodes in a subtree rooted with this node
void BTreeNode::traverse()
{
// There are n keys and n+1 children, travers through n keys
// and first n children
int i;
for (i = 0; i < n; i++)
{
// If this is not leaf, then before printing key[i],
// traverse the subtree rooted with child C[i].
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i];
}
// Print the subtree rooted with last child
if (leaf == false)
C[i]->traverse();
}
// Function to search key k in subtree rooted with this node
BTreeNode *BTreeNode::search(int k)
{
// Find the first key greater than or equal to k
int i = 0;
while (i < n && k > keys[i])
i++;
// If the found key is equal to k, return this node
if (keys[i] == k)
return this;
// If key is not found here and this is a leaf node
if (leaf == true)
return NULL;
// Go to the appropriate child
return C[i]->search(k);
}
// The main function that inserts a new key in this B-Tree
void BTree::insert(int k)
{
// If tree is empty
if (root == NULL)
{
// Allocate memory for root
root = new BTreeNode(t, true);
root->keys[0] = k;
// Insert key
root->n = 1;
// Update number of keys in root
}
else // If tree is not empty
{
// If root is full, then tree grows in height
if (root->n == 2*t-1)
{
// Allocate memory for new root
BTreeNode *s = new BTreeNode(t, false);
// Make old root as child of new root
s->C[0] = root;
// Split the old root and move 1 key to the new root
s->splitChild(0, root);
// New root has two children now.
Decide which of the
// two children is going to have new key
int i = 0;
if (s->keys[0] < k)
i++;
s->C[i]->insertNonFull(k);
// Change root
root = s;
}
else
// If root is not full, call insertNonFull for root
root->insertNonFull(k);
}
}
// A utility function to insert a new key in this node
// The assumption is, the node must be non-full when this
// function is called
void BTreeNode::insertNonFull(int k)
{
// Initialize index as index of rightmost element
int i = n-1;
// If this is a leaf node
if (leaf == true)
{
// The following loop does two things
// a) Finds the location of new key to be inserted
// b) Moves all greater keys to one place ahead
while (i >= 0 && keys[i] > k)
{
keys[i+1] = keys[i];
i--;
}
// Insert the new key at found location
keys[i+1] = k;
n = n+1;
}
else // If this node is not leaf
{
// Find the child which is going to have the new key
while (i >= 0 && keys[i] > k)
i--;
// See if the found child is full
if (C[i+1]->n == 2*t-1)
{
// If the child is full, then split it
splitChild(i+1, C[i+1]);
// After split, the middle key of C[i] goes up and
// C[i] is splitted into two.
See which of the two
// is going to have the new key
if (keys[i+1] < k)
i++;
}
C[i+1]->insertNonFull(k);
}
}
// A utility function to split the child y of this node
// Note that y must be full when this function is called
void BTreeNode::splitChild(int i, BTreeNode *y)
{
// Create a new node which is going to store (t-1) keys
// of y
BTreeNode *z = new BTreeNode(y->t, y->leaf);
z->n = t - 1;
// Copy the last (t-1) keys of y to z
for (int j = 0; j < t-1; j++)
z->keys[j] = y->keys[j+t];
// Copy the last t children of y to z
if (y->leaf == false)
{
for (int j = 0; j < t; j++)
z->C[j] = y->C[j+t];
}
// Reduce the number of keys in y
y->n = t - 1;
// Since this node is going to have a new child,
// create space of new child
for (int j = n; j >= i+1; j--)
C[j+1] = C[j];
// Link the new child to this node
C[i+1] = z;
// A key of y will move to this node. Find location of
// new key and move all greater keys one space ahead
for (int j = n-1; j >= i; j--)
keys[j+1] = keys[j];
// Copy the middle key of y to this node
keys[i] = y->keys[t-1];
// Increment count of keys in this node
n = n + 1;
}
// Driver program to test above functions
int main()
{
BTree t(3); // A B-Tree with minium degree 3
t.insert(10);
t.insert(20);
t.insert(5);
t.insert(6);
t.insert(12);
t.insert(30);
t.insert(7);
t.insert(17);
cout << "Traversal of the constucted tree is ";
t.traverse();
int k = 6;
(t.search(k) != NULL)? cout << "nPresent" : cout << "nNot Present";
k = 15;
(t.search(k) != NULL)? cout << "nPresent" : cout << "nNot Present";
return 0;
}

B+树代码太长，就不放这里了。

算法分析

B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。

B+ 树的优点在于：

由于B+树在内部节点上不好含数据信息，因此在内存页中能够存放更多的key。数据存放的更加紧密，具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。
B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。

哈希查找

基本思想

哈希查找也叫散列查找，整个散列查找过程大概分两步：在存储时通过散列函数计算记录的散列地址，并按此散列地址存储该记录。当查找时，一样通过散列函数计算记录的散列地址，然后访问散列地址的记录。

散列函数构造的方法

（1）直接定址法： 取关键字的某个线性函数值为散列地址，需要事先知道关键字的分布情况，适合查找表较小且连续的情况。

（2）数字分析法：使用关键字的一部分来计算散列存储的位置。适合处理关键字位数较大的情况。

​ （3）平方取中法：假设关键字是1234，那它的平方就是1522756，再抽取中间的3位就是277，适合不知道关键字的分布，而位数又不是很大的情况。

（4）折叠法： 将关键字从左到右分割成位数相等的几个部分，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。比如关键字是9876543210，散列表表长为三位，我们将它分成四组，987|654|321|0，然后将他们叠加求和等于1962，再求后三位得到散列地址962。 适合事先不知道关键字的分布，关键字位数叫多的情况。

5）除留余数法：此方法为最常用的构造散列函数的方法

处理冲突散列的方法：

1：开放定址法就是一旦出现了冲突，就去寻找下一个空的散列地址，只要散列地址够大，空的散列地址总会被找到

2再散列函数法：事先准备多几个散列函数

​ 3：链地址法：将所有同关键字的记录存储在一个单链表中，称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。

代码实现

//哈希查找
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct hash
{
int nValue;
int nIndex;
struct hash *pNext;
}HashTable;
//造哈希表
HashTable **CreateHashTable(int arr[],int nLength)
{
if(arr == NULL || nLength <= 0) return NULL;
//申请表头
HashTable **pHash = NULL;
pHash = (HashTable **)malloc(sizeof(HashTable*)*nLength);
memset(pHash,0,sizeof(HashTable*)*nLength);
//元素入表
int nIndex;
int i;
HashTable *pTemp = NULL;
for(i = 0;i < nLength;i++)
{
nIndex = arr[i]%nLength;
pTemp = (HashTable*)malloc(sizeof(HashTable));
pTemp->nValue = arr[i];
pTemp->nIndex = i;
pTemp->pNext = pHash[nIndex];
pHash[nIndex] = pTemp;
}
return pHash;
}
int HashSearch(HashTable **pHash,int nLength,int nNum)
{
if(pHash == NULL || nLength <=0) return -1;
int nIndex;
HashTable *pTemp = NULL;
//找到对应的链表
nIndex = nNum%nLength;
pTemp = pHash[nIndex];
while(pTemp)
{
if(pTemp->nValue == nNum)
{
return pTemp->nIndex;
}
else
{
pTemp =pTemp->pNext;
}
}
return -1;
}
int main()
{
int arr[] = {101,12,15,12,11,45,78,1};
HashTable **pHash = CreateHashTable(arr,sizeof(arr)/sizeof(arr[0]));
int nIndex = HashSearch(pHash,sizeof(arr)/sizeof(arr[0]),1);
printf("%dn",nIndex);
return 0;
}

算法分析

O(1)

时间复杂度大对比

1、顺序查找：
（1）最好情况：要查找的第一个就是。时间复杂度为：O(1)
（2）最坏情况：最后一个是要查找的元素。时间复杂度未：O(n)
（3）平均情况下就是：（n+1）/2。
所以总的来说时间复杂度为：O(n)
2、二分查找：O(log2n)->log以2为底n的对数
解释：2^t = n; t = log(2)n;
3、插值查找：O(log(2)(log(2)n))->log以2为底的（log以2为底的n的对数）的对数
4、斐波那契查找：O(log2n)->log以2为底n的对数
5、树表查找：
（1）二叉树：O(log2n)~O(n)之间
（2）红黑树：O(lgn)
（3）B和B+树：O(log2n)
6、分块查找：O(log2n)~O(n)之间
7、哈希查找：O(1)

最后

以上就是俭朴百褶裙为你收集整理的查找算法总结查找算法详解的全部内容，希望文章能够帮你解决查找算法总结查找算法详解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。