查找算法

线性表查找

顺序查找

算法介绍

顺序查找算法又称顺序搜索算法或者线性搜索算法，是所有查找算法中最基本、最简单的，对应的时间复杂度为O(n)。

顺序查找算法适用于绝大多数场景，既可以在有序序列中查找目标元素，也可以在无序序列中查找目标元素。

顺序查找的特点：

• 方法简单
• 对表的结构无要求
• 查找效率低，当n较大时不宜采用

算法实现

实现思路：所谓顺序查找，指的是从待查找序列中的第一个元素开始，查看各个元素是否为要找的目标元素。若相同则查找成功返回对应数组下标；若遍历完整个数组也没有找到待查找元素，则说明查找失败，返回-1。

一个简单的顺序查找，其实就是一个for循环
    
int search(int arr[N],int value)
{
    
    for(int i=0;i<N;i++)
    {
        if(arr[i]==value)
         return i;
	}
    //匹配失败，返回-1
    return -1;
}

效率分析

时间复杂度：

• 最坏情况：若相同则查找成功返回对应数组下标；若遍历完整个数组也没有找到待查找元素，则说明查找失败，返回-1。
• 最好情况：最理想的情况就是待查找元素位于集合的第一个位置，程序只需执行一次循环和比较就成功找到待查找元素并返回退出，所以时间复杂度为O(1)。
• 平均情况：综合两种，顺序查找的时间复杂度为O(n)。

空间复杂度：

• 算法中只需设置一个临时变量用于控制循环次数和数组下标变化，没有借助额外的辅助空间，所以空间复杂度为O(1)。

二分查找

算法介绍

二分查找，又叫折半查找，通过找到数据二段性每次都能将原来的数据筛选掉一半，通过这个算法我们能够将一个一个查找的 O(n) 的时间复杂度优化到 O(log2n) ，极大地提升了查找的效率。

但使用二分进行查找必须要有一个前提，那就是查找的区间必须是有序的。如数组并非有序，则找不到该数组的的二段性。

二分查找的特点：

• 效率较高
• 要求查找表有序
• 只适合顺序查找和建立后很少改动而只需要查找的表

算法实现

实现思路：

二分法的思想很简单，因为整个数组是有序的，数组默认是递增的。

• 首先选择数组中间的数字mid和需要查找的目标值比较
• 如果相等最好，就可以直接返回答案了
• 如果不相等
  • 如果中间的数字大于目标值，则中间数字向右的所有数字都大于目标值，全部排除，再移动right到mid-1的位置
  • 如果中间的数字小于目标值，则中间数字向左的所有数字都小于目标值，全部排除，再移动left到mid+1的位置

#include <stdio.h>
#include <string.h>

int searchKey(KeyType key,SSTable ST)
{

    int left=0,right = ST.length;
    /*区间初值*/
    while(left<=right)//一定要取等，最后left和right相等时为最后一种情况
    {
        mid = (left+right)/2 //找到中间元素
        if(key == ST.elem[mid].key)
        {
            return mid;
        }
        else if(key < ST.elem[mid].key)
        {
            right = mid-1;//key在middle左边，将right移过来
        }
        else 
        {
            left = mid+1;//key在middle右边，将left移动过来
        }
    }
    return 0;
}

效率分析

• 时间复杂度：O(log2n)

• 空间复杂度：O(1) 或 O(log2n)，取决于二分查找的实现方式。如果使用迭代的方式，只需要一个变量来存储中间元素的下标，所以空间复杂度为 O(1)。如果使用递归的方式，每次递归调用都需要额外的栈空间，所以空间复杂度为 O(log2n)。

二分查找的优点和缺点分别是：

• 优点：比较次数少，查找速度快，平均性能好。
• 缺点：要求待查表为有序表，且插入删除困难。

分块查找

算法介绍

分块查找也称为索引查找，分块查找是一种结合了二分查找和顺序查找的查找方法，它将数据分为若干个块，在索引查找法中，除表本身之外还需要建立一个索引表。由分块查找可知，它要分开进行，块内元素之间无大小关系，块与块之间有大小关系（比如说：第二块中的元素肯定要比第一块中大，第三块中元素肯定要比前两块中的元素大）所以索引表是有序的，但每一块中的元素无序，可以进行二分查找进行查找由于要有索引所以要用到结构体。

算法实现

索引查找是在一定条件下使用（给索引表开值为3，代表查找表中元素个数要是3的倍数），则每个块中的元素个数为n/3,则在每个块中找出块中最大值，赋值给索引表，在对索引表的关键字进行比较排序

索引查找是先找到确定的块（这个过程可以进行二分也可以进行顺序查找（下边代码实现的是顺序查找））

确定块之后在块中进行顺序查找

分块查找代码示例:
#include <stdio.h>
#include <stdlib.h>

// 定义块的结构体
struct index {
    int key; // 块的最大值
    int start; // 块的起始位置
};
/*索引表中的每个元素包括该块中的最大值和块的起始位置*/

// 定义全局变量，存储索引表
struct index newIndex[3];

// 定义分块查找函数，参数为待查元素和数据数组
int blockSearch(int key, int arr[]) {
    // 定义变量，存储左右边界和中间位置
    int left, right, mid;
    // 初始化左右边界(索引表的)
    left = 0;
    right = 2;
    // 1.二分查找：在索引表中用二分查找确定待查元素所在的块
    while (left <= right) {
        // 计算中间位置
        mid = (left + right) / 2;
        // 如果找到了所在的块，跳出循环
        if (key <= newIndex[mid].key)
        {
            break;
        // 如果待查元素大于中间位置的最大值，由于是有序的，索引说明只能在在右半部分，更新左边界
        } else
        {
            left = mid + 1;
        }
    }
    // 如果没有找到所在的块，返回-1表示查找失败
    if (left > right)
    {
        return -1;
    }
    // 在确定的块中用顺序查找找到待查元素
    // 获取块的起始位置和结束位置
    int start = newIndex[mid].start;
    int end = start + 5;
    // 2.顺序查找：遍历块中的元素，如果找到了待查元素，返回其位置
    for (int i = start; i <= end; i++) 
    {
        if (arr[i] == key)
        {
            return i;
        }
    }
    // 如果没有找到待查元素，返回-1表示查找失败
    return -1;
}

int main() {
    // 定义数据数组
    int arr[] = {33, 42, 44, 38, 24, 48, 22, 12, 13, 8, 9, 20, 60, 58, 74, 49, 86, 53};
    // 定义变量，存储块的数量和数据的总个数
    int m = 3;
    int n = 18;
    // 定义变量，为每个块内的元素个数
    int size = n / m;
    // 定义变量，存储待查元素
    int key;
    // 确定每个块的最大值和起始位置
    for (int i = 0; i < m; i++) 
    {
        // 初始化每个块的起始位置
        newIndex[i].start = i * size;
        // 初始化每个块的最大值为第一个元素的值
        newIndex[i].key = arr[i * size];
        // 遍历每个块中的元素，更新每个块的最大值
        for (int j = i * size; j < (i + 1) * size; j++)
        {        /*条件为下个块之前*/
            if (newIndex[i].key < arr[j]) 
            {
                newIndex[i].key = arr[j];//更新每个块的最大值
            }
        }
    }
    // 输入待查元素
    printf("请输入要查找的元素：\n");
    scanf("%d", &key);
    // 调用分块查找函数，获取结果
    int result = blockSearch(key, arr);
    // 输出结果
    if (result == -1) 
    {
        printf("查找失败，没有找到该元素。\n");
    } 
    else
    {
        printf("查找成功，该元素在数组中的位置是：%d\n", result + 1);
    }
    return 0;
}

效率分析

• 时间复杂度：O(log2m + n/m)，其中 m 是块的数量，n 是数据的总个数，n/m为每个块元素个数。这是因为在分块查找过程中，需要先在索引表中用二分查找或顺序查找确定待查元素所在的块，这一步的时间复杂度为 O(log2m) 或 O(m)；然后在已确定的块中用顺序查找找到待查元素，这一步的时间复杂度为 O(n/m)。因此，分块查找的总时间复杂度为 O(log2m + n/m) 或 O(m + n/m)。
• 空间复杂度：O(m)，这是因为分块查找需要额外的空间来存储索引表，索引表的大小为 m。

• 优点：插入删除比较容易，无需进行大量移动。如果线性表既要快速查找又经常动态变化，则可采用分块查找。
• 缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算。如果分块过于稀疏或过于密集，都会影响查找效率。

树表的查找

二叉排序树

二叉排序树-介绍

二叉排序树又称为二叉搜索树、二叉查找树。二叉排序树或是空树，或是满足如下性质的二叉树：

• 若它的左子树非空，则左子树上所有结点的值均小于它根结点的值。
• 若它的右子树非空，则右子树上所有结点的值均大于它根结点的值。
• 它的左、右树又本身是一颗⼆叉排序树

二叉排序树性质：

中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的递增有序序列，即结点的从小到大顺序。

二叉排序树-查找

查找思路：

• 若查找的关键字等于根节点，查找成功
• 若查找的关键字不等于根节点
  • 小于根节点，查找其左子树
  • 若大于根节点，查找其右子树
• 再左右子树上的查找与其类似

typedef struct{
    KeyType key; //关键字项
    infoType otherinfo;//其他数据域
}ElemType;

typedef struct BSTNode{
    ElemType data;
    struct BSTNode* lchild;//左孩子
    struct BSTNode* rchild;//右孩子
}BSTNode,*BSTree;

BSTree T;//定义二叉排序树T

二叉排序树的递归查找算法思想：

1. 若二叉排序树为空，则查找失败，直接返回空指针。
2. 若二叉排序树非空，将给定值key与根结点的关键字进行比较如果成功返回根结点地址，若小于data.key则查找左子树，若data.key则查找右子树。

/*二叉排序树递归查找函数*/

BSTree searchBST(BSTree T,KeyType key)
{
    
    if(key==T->data.key||T==NULL)//树为空或找到了直接返回
    {
        return T;
    }
    else if(key<T->data.key)
    {
        return searchBST(T->lchild,key);//在左子树中继续寻找
    }
    else
    {
       return searchBST(T->rchild,key); //在右子树中继续寻找
    }
}

二叉排序树的平均查找长度(ASL)和树的形态有关，一般来说树的高度越高，平均查找长度越大

时间复杂度最好情况为O(log2n)，树的深度为：[log2n]+1，此时与折半查找中的判定树相同.

时间复杂度最坏为O(n)，树的深度为n，插入的元素变成了单支树的形态

问题: 如何提高形态不均衡的二叉排序树的查找效率？

解决方法：做“平衡化”处理，尽量让二叉树的形状均衡。即实现平衡二叉树

二叉排序树-插入

生成二叉排序树的过程就是插入的过程

插入思路：

• 若二叉排序树为空，则插入结点作为根节点插入到空树中

• 若二叉排序树为非空，则在其左右子树上查找

  • 树中已有，不再插入，直接返回
  • 树中没有，查找直到某个叶子结点的左子树或右子树为空位置，再将该节点插入为该叶子结点的左孩子或右孩子

  插入的结点一定是叶子结点上

bool insert(int key)
{
    
   	//定义一个临时指针 用于移动
	tNode* temp = root;//temp为插入位置的结点
	tNode* prev = NULL;//定位到待插入位置的前一个结点
    
    if(root==NULL)
    {
        root = (tNode*)malloc(sizeof(tNode));
		root->data = key; 
		root->left = NULL; 
		root->right = NULL; 
    }//若根节点为NULL，直接插入
    
    else
    {
    /*第一部分：找到要插入的位置*/
	while (temp != NULL)
	{
		prev = temp; //保存插入结点的双亲的位置
		if (key < temp->data)
		{
			temp = temp->left;//找左边子树，若移动后为空则代表找到了插入的位置
		}
		else if(key > temp->data)
		{
			temp = temp->right;//找右边子树，移动后为空则代表找到了插入位置
		}
		else
		{
            printf("已存在该结点");
			return false;//存在该结点直接返回插入失败
		}
	}
    /*第二部分：插入结点*/
    
    /*当结点左子树为空时*/
	if (key < prev->data)
	{
		prev->left = (tNode*)malloc(sizeof(tNode));
		prev->left->data = key; //插入结点数据域
		prev->left->left = NULL; //设置左孩子为空
		prev->left->right = NULL; //设置右孩子为空
	}
    /*当结点右子树为空时*/
	else
	{
		prev->right = (tNode*)malloc(sizeof(tNode));
		prev->right->data = key;
		prev->right->left = NULL;
		prev->right->right = NULL;
	}
        
    }
    
    printf("插入成功");
    return true;
}

注意：

不同插入次序的序列生成不同形态的二叉排序树。

二叉排序树-删除

在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下来，将因删除结点而断开的二叉链表重新链接起来，同时**确保二叉排序树的性质（左子树结点值＜根结点值＜右子树结点值）**不会丢失。

删除操作一般会出现三种情况：

1. 若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质。
2. 若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置。
3. 若结点z有左、右两棵子树，有两种方法：

• 令z的直接前驱（或直接后继）替代z，然后从二叉排序树中删除这个直接后继或直接前驱，这样就转换成了第一或第二种情况，按照第一种或第二种情况再删除直接前驱或后继(常使用这种方法)。
• 先用z结点的左子树替代该结点，再将z结点的右子树作为z节点直接前驱的右子树（这种方法会可能会增加树的深度，常使用第一种方法处理）

注：

已知二叉排序树经过中序遍历可以得到一个递增的有序序列，这里的直接后继（或直接前驱）应该是指被删除结点在这个中序遍历序列中的直接后继（或直接前驱）。
 
体现在二叉排序树的图中:
 某个结点的直接后继为以该结点为根的右子树中最左下位置的结点，即右子树的最小值；
 某个结点的直接前驱为以该结点为根的左子树中最右下位置的结点，即左子树的最大值。

/*从二叉树中删除值为key的结点*/
bool deleteNode(BSTree &T,KeyType key)
{
    BSTree p = T，temp = NULL, prior = NULL;
    
    /*先查找值为key的结点*/
    while(p)
    {
        if(p->data.key == key)
            break;//查找成功
        else if(p->data.key < key)
        {
            p = p->rchild;//在右子树中寻找
        }
        else
        {
            p = p->lchild;//在左子树中寻找
		}
    }
    
    if(!p)
    {
        return false; //找不到结点p为NULL，直接返回
    }
    
    if(p->lchild==NULL && p->rchild==NULL)//p为叶子结点
    {
        p = NULL;
    }
    
    else if(p->lchild==NULL) //p左子树为空，删p后重接右子树
    {
        temp = p;
        p = p->right;
        free(temp);
    }
    
    else if(p->rchild==NULL)//p右子树为空，删p后重接左子树
    {
        temp = p;
        p = p->left;
        free(temp);
	}
    
    else//左右子树均不为空,先找前驱结点
    {
        temp = p;
        temp = temp->lchild;//在左子树中寻找最大值，即删除结点的直接前驱
        
        while(temp->rchild)//右子树为空时，找到结点退出循环
        {
            prior = temp;
            temp = temp->rchild;//继续寻找
		}
        //while循环结果后：temp为直接前驱，prior为temp的双亲
        p->data.key = temp->data.key;
        //将删除的结点替换为直接前驱
        
        if(prior!=p)//直接前驱的双亲不为删除的结点时,前驱右孩子为NULL
        {
            /*将直接前驱的左孩子重挂到双亲的右孩子上去，替代直接前驱的位置*/
            prior->rchild = temp->lchild;
        }
        
        else//直接前驱的双亲为删除结点时,前驱右孩子为NULL
        {
            /*直接将前驱的左子树(右子树为空)重挂到双亲的左子树上去替代直接前驱的位置*/
            prior->lchild = temp->lchild;
        }
        
        free(temp);//删除直接前驱
    }
    return true;
}

平衡二叉树