int Sequential_Sreach(int* a, int key, int n)  //a为传入的数组；key为需要查找的元素；
{                                              //n为数组元素个数；
	for (int i = 0; i < n; i++)
	{
		if (a[i] == key)
			return i;
	}
	return 0;         //若没有找到，则返回0；
}

2.2 优化改进

上述方法，每进入一次循环都要判断 i 是否越界，接下来介绍一个改进后的代码：若要查找数组下标从1到n中的某个元素，设置一个哨兵，每次与该哨兵比较，一起通过代码来理解??

int Sequential_Sreach(int* a, int key, int n)
{
	a[0] = key;
	int i = n;
	while (a[i] != key)
	{
		i--;
	}
	return i;              
}

※

与之前不一样的是这里是找下标1到n中的元素，将a[0]赋值需要查找的数，从右往左查找，进入while循环，减去下标 i 直到a[ i ] ==key;

若当数组中没有查到到，此时i = 0，跳出while循环，return 0；

2.3 例题：移除元素?

?LeetCode? 27.移除元素https://leetcode.cn/problems/remove-element/

给你一个数组 nums?和一个值 val，你需要原地移除所有数值等于?val?的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

?审题：最开始做这道题的时候可能会轻敌，移除元素不就只需要将查找到的元素删除吗，但这是个数组，并且题目要求返回删除后的长度，所以每次删除一个元素，需要将其后面的所有元素往前移一位，像这样你可以很简单的将其暴力地解出，但是效率会很低；这里我们介绍一个做题时常用且巧妙地方法：双指针（左右指针）

解题：

（1）定义 left ， right 指向同一数组，需要查找的元素? val；

（2）※for循环中，right遍历整个数组，若right指向的元素等于 val，则left保持原来位置（该位置值为val，待覆值），right指向下一位置；

? ? ? ? ※ 当right指向的元素不为val时，将此时的值赋给left指向的值，就将原本为val的值覆盖了

（3）※??left为数组下标，最后left指向的是left+1个数，但移除后的的个数为left；?

int removeElement(int* nums, int numsSize, int val){
    int left = 0;
    for(int right = 0; right<numsSize;right++)
    {
        if(nums[right] != val)
        {
            nums[left] = nums[right];
            left++;
        }
    }
    return left;
}

?图解：

三、有序表查找

?如果说顺序表是从一堆衣服中找到你想要的，那么有序表就是从从小到大的套娃中找到想要的大小；🤔

3.1 二分查找

?折半查找又称折半查找，顾名思义就是将一个有序的数组（升序）一中间数为“折痕”，将其折为两部分，左部分数小，右部分数大，联想二叉树，也是类似的二分法；

查找：

若其大于中间数（mid），则在右部分（反之，则在左部分）；

之后再将mid+1作为右部分的左边界（mid-1作为左部分的右边界），再一次找出该部分的中间值；

重复以上步骤，直至 mid 为要查找的值??

int Binary_Sreach(int* a, int key, int n )
{
	int left = 0;
	int right = n - 1;
	int mid;
	while (left <= right)
	{
		mid = (left + right) / 2;   //  [left,mid-1] [mid] [mid+1,right]
		if (mid > key)
			right = mid-1;

		else if (mid < key)
			left = mid+1;

		else
			return mid;

	}
	return 0;
}

?时间复杂度：O（logn）

3.2 *插值查找

插值查找算是折半查找的优化，折半查找中mid=（left + right）/ 2,即

mid = left+（1/2）*（right - left）

插值查找就是将上方公式中的1/2改成（key-a[left]）/（a[right] - a[left]）,则：

mid = left +?（key - a[left]）/（a[right] - a[left]）

这样之后查找的效率提升了，但是二叉查找还是相对稳定一些；

四、散列表查找（哈希表）

4.1 初步了解

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?参考文献：《大话数据结构》

设想你进入图书馆，如果你是社恐，肯定会像顺序表查找一样，在一个个书架里查找你想要的书，这样效率肯定会很差；但如果你善于社交，向图书管理员询问这本书的名字（key），那么他肯定会迅速的锁定这本书的地址，最后将书找出来给你。

就像询问图书管理员一样，我们通过一个函数，该函数满足：

储存位置 = f（key）

又因为自变量key与因变量是一一对应的，所以每输入一个key的值，就会对应一个储存位置；

※我们把这个对应关系 f 称为散列函数，又称为哈希(Hash) 函数。按这个思想，将所有函数值及储存位置记录在一块连续的储存空间中，将其称为哈希表或是散列表，

※那么关键字（key）对应的记录存储位置我们称为散列地址。

4.2 哈希表的运用

通过以上的了解，我们可以发现，哈希表可以用来储存也可以用来查找，在做题中大部分使用来储存的；废话不多说，我们用例题来深入的解析??

（1）初阶

LeetCode 1748.唯一元素的和https://leetcode.cn/problems/sum-of-unique-elements/submissions/

给你一个整数数组?nums?。数组中唯一元素是那些只出现?恰好一次?的元素。请你返回?nums?中唯一元素的?和?。

示例 1：
输入：nums = [1,2,3,2]
输出：4
解释：唯一元素为 [1,3] ，和为 4 。

思路分析：

? 这一题是一个非常明显的用哈希表计数的题，数组中每个元素作为key，用其指向哈希表中的一个储存空间；

? 简单的来说，就是用nums中的数作为哈希表的下标，遍历一遍nums，对每一个数对应指向哈希表的位置+1，则nums中恰好出现一次的数指向哈希表中的数为1，最后遍历哈希表中的数，判断其是否为1就行了

代码如下??

int sumOfUnique(int* nums, int numsSize) {
	int hash[101];
	memset(hash, 0, sizeof(hash));   
        //创建哈希表，因为nums数组的数范围为1-100；所以哈希表中需要啊有101个空间
	
    for (int i = 0; i < numsSize; i++)
	{
		hash[nums[i]]++;          //nums[i]的值作为哈希表的下标
	}
    int sum = 0;
	for (int j = 1; j <= 100; j++)
	{
		if (hash[j] == 1)
			sum += j;              //由上可知，j为nums数组的值，所以直接加在sum中就行了

	}
	return sum;
}

个人总结：

以我自己来看，哈希表就相当于我们数学里学的复合函数??g?( f?( x ) ) ,重点在于内函数的值作为外函数的变量。

接下来我们再通过一题来进一步熟练哈希表：

（2）中阶

??????2206. 将数组划分成相等数对 - 力扣（LeetCode）

给你一个整数数组?nums?，它包含?2 * n?个整数。

你需要将?nums 划分成?n?个数对，满足：

每个元素 只属于一个 数对。
同一数对中的元素相等?。
如果可以将 nums?划分成 n?个数对，返回 true?，否则返回 false?。

示例 1：

输入：nums = [3,2,3,2,2,2]
输出：true
解释：
nums?中总共有 6 个元素，所以它们应该被划分成 6 / 2 = 3 个数对。
nums 可以划分成 (2, 2) ，(3, 3) 和 (2, 2)?

思路分析：

? 由题可知，每个数对有两个数组成且这两个数相等，所以再nums数组中，同一元素的个数一定是偶数；

? 所以用哈希表来记录同一元素的个数，最后判断其是否为偶数就行了

代码如下??

bool divideArray(int* nums, int numsSize){
    int hash[501];
    memset(hash,0,sizeof(hash));
    for(int i = 0;i<numsSize;i++)
    {
        hash[nums[i]]++;        //记录某一元素的个数，该元素为哈希表的下标
    }
    for(int j = 0;j<numsSize;j++)
    {
        if(hash[nums[j]] % 2 != 0)
        return false;               //若nums中有一个元素的个数不为偶数，则返回假

    }
    return true;      //若哈希表中所有元素均为偶数，则返回真
}

（3）高阶?

817. 链表组件

给定链表头结点?head，该链表上的每个结点都有一个 唯一的整型值 。同时给定列表?nums，该列表是上述链表中整型值的一个子集。

返回列表?nums?中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表?nums?中）构成的集合。

示例：

?

输入: head = [0,1,2,3,4], nums = [0,3,1,4]
输出: 2
解释: 链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。

思路分析：

??首先这道题读题读懂是非常重要的，通过题我们可以知道，这道题简单的来说就是将数组对应链表，能将数组分成多少段子链表；

? 像这种有映射关系的题我们就可以试着用哈希表来解决：

解题步骤：

? 创建哈希表，首先要知道哈希表的空间，因为数组是链表中整型值的子集，哈希表的空间不能直接是numsSize，要用数组里的值作为哈希表的下标，再用链表中的值找到其下标对应的值，所以哈希表的空间大小是链表的长度

int LisrSize(struct ListNode* head)
{
	struct ListNode* cur = head;
	int size = 0;
	while (cur != NULL)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

? 所以说第一步是求出链表长度??，然后创建哈希表；

? 之后遍历数组，对于数组中出现的数，我们将它作为哈希表的下标位置，对该位置的值+1；

? 最后一步，遍历链表，判断链表中的整型值对应哈希表的位置是0还是1，0即为断开之处，1即为链接之处。加上计数，这道题就完成了。👌

我们看看代码如何实现??

int numComponents(struct ListNode* head, int* nums, int numsSize) {
	int Lsize = LisrSize(head);   //求链表长度
	int hash[Lsize]; 
	memset(hash, 0, sizeof(hash));     //创建哈希表
	for (int i = 0; i < numsSize; i++)
	{
		hash[nums[i]]++;
	}
	int ret = 0;           
	while (head != NULL)
	{
		if (head != NULL && hash[head->val] == 1)   //出现1，则计数一次
			ret++;       
		while (head != NULL && hash[head->val] == 1)
		{
			head = head->next;           //将这一小段走完，走到断开处0
		}
        if (head != NULL )         //  ※每次head->next都需判断是否指向NULL
        head = head->next;         //走到断开处0之后，再去寻找下一个开端1
	}
	return ret;
}