初识数组查找（顺序查找法和二分查找法）

先来了解一下查找是干什么的？查找就是给定一个值，然后在大量信息中寻找这个特定的值。在计算机应用中，查找是常用的基本算法，一般有七大查找算法，分别为：顺序查找、二分查找、插值查找、斐波那契查找、树表查找、分块查找、哈希查找。
今天，forever 也是初识查找算法，就先来说说顺序查找和二分查找吧！

查找原理：顺序查找也叫线性查找，就是从数组的开头开始顺序扫描，依次将其扫描值与其给定值比较。若相等则查找成功；若扫描结束，仍未找到该值，则查找失败。

1.C语言线性查找实现顺序数组查找对应数值

//线性查找实现顺序数组查找
#define _CRT_SECURE_NO_WARNINGS 1//vs2019编译器运行头文件
#include
int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9 };    //定义数组
	int k = 0,i=0;
	int count = 0;        //定义一个计数变量
	int let = sizeof(arr)/sizeof(arr[0]);    //计算数组长度
	scanf("%d", &k);     //输入一个需要查找的值
	for (i = 0; i < let; i++)      //利用循环
	{
		if (arr[i] == k)
		{
			count++;
			printf("查找成功，其下标为：%dn", i);
			break;           //找到后就不再进行查找直接利用break跳出循环
		}
	}
	if (count == 0)
	{
		printf("查找失败！");
	}
	return 0;
}

运行结果：

线性查找顺序数组，算法思想简单，但是要从头开始挨个查找，直至找到为止。
2.C语言线性查找实现乱序数组查找对应数值

#define _CRT_SECURE_NO_WARNINGS 1
#include
int main()
{
	int arr[] = { 1,4,5,2,3,6,9,8,7 };//这里是乱序数组
	int k = 0,i=0;
	int count = 0;
	int let = sizeof(arr)/sizeof(arr[0]);
	scanf("%d", &k);
	for (i = 0; i < let; i++)
	{
		if (k == arr[i])
		{
			count++;
			printf("查找成功，其下标为：%dn", i);
			break;
		}
	}
	if (count == 0)
	{
		printf("查找失败！n");
	}
	return 0;
}

运行结果：

线性查找既适用于顺序数组，也使用用于乱序数组。
线性查找优点：算法简单，易于实现，适用于顺序结构和链式结构。
线性查找复杂程度：0(n)—较复杂，最多要比较 n+1 次，平均查找长度大，效率低。

查找原理：二分查找也叫折半查找，使用二分查找时元素必须有序，无序则要先排序在进行查找。二分查找是首先定义一个变量如 left 存放数组开头值，再定义一个变量 right 存放数组结尾值，然后定义一个变量 mid 存放 (left+right)/2 作为中间值。查找首先从中间开始查找，如果中间值刚好是需要查找值，则查找成功；如果需要查找值大于或小于中间值：若大于，则排除中间值前面的所有值再从中间值后到结尾值这个范围内继续进行查找；若小于，则排除中间值后面的所有值再从中间值前到开头值这个范围内开始查找。每次淘汰一半，缩小一个范围就会更改一次中间值，若直到某一个范围中间值查找为空，则无法找到给定值，查找失败。

1.二分查找法流程图
2.C语言实现数组查找对应数值

//二分查找实现数组查找
#define _CRT_SECURE_NO_WARNINGS 1
#include
int main()
{
	int ls[] = { 1,2,3,4,5,6,7,8,9 };
	int a = 0;
	int left = 0,right = 0;
	int mid = 0;
	int n = sizeof(ls)/sizeof(ls[0]);
	scanf("%d", &a);
	right = n - 1;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (a > ls[mid])
		{
			left = mid + 1;
		}
		if (a < ls[mid])
		{
			right = mid - 1;
		}
		if (a == ls[mid])
		{
			printf("查找成功，其下标为：%dn", mid);
			break;
		}
	}
	if (left > right)
	{
		printf("查找失败n");
	}
	return 0;
}

运行结果1：

运行结果2：

二分查找法优点：查找效率高，适用于数据量很大时使用。
二分查找法复杂程度：0( log2(n) )—最多查找 log2(n+1)次，但是必须要求所查找数组是有序的。
二分法查找容易出现的错误：
1.

	mid = (left + right) / 2;
	while (left <= right)
	{
		//mid = (left + right) / 2;

注意：这里无法运行和查找，错误原因：将 mid 赋值放在了循环外面，会导致出现死循环，因此无法进行查找。
2.

mid = (left + right) / 2;
		if (a > ls[mid])
		{
			left = mid;
		}
		if (a < ls[mid])
		{
			right = mid;
		}

注意：这里给 left 赋值为 mid 而不是 mid+1,给 right 赋值为 mid 而不是 mid-1 ，对查找其他值无影响，但是数组最后一个值无法查找到。
这是我对顺序查找（线性查找）和二分查找（折半查找）的一些认识和见解，二分查找一定要注意常见容易出现的错误。
目前就这些，还烦请大佬指点一番！
谢谢观看，再见！

代码都可以运行，所用编译器 vs2019 ,运行时注意加上编译头文件#define _CRT_SECURE_NO_WARNINGS 1