服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - C语言编程之初识数组线性查找和二分查找

C语言编程之初识数组线性查找和二分查找

2022-01-07 14:26Booksort C/C++

本篇文章是C语言编程篇,主要为大家介绍C语言编程中数组的线性查找及二分查找分析讲解,有需要的朋友可以借鉴参考下,希望可以有所帮助

先来了解一下什么是查找,

额,好吧,这没什么可了解的,

就是查找数组中的某个元素的位置或是否存在。

就这,没了。直接了解查找算法吧。

线性查找

线性查找与二分查找有些差别。
数组内元素可以是混乱无序的,即没有按顺序储存。这方法很简单,就是从首元素开始,依此向后查找,比较。仅此而已。运用循环,依次对比。
看代码吧。

#include <stdio.h>
int main(void)
{
	int arr[] = { 5,4,6,8,7,9,10,2,3,1 };
	int len = sizeof(arr) / sizeof(arr[0]);//计算数组的元素个数
	int i;
	int n;
	scanf("%d", &n);//输入要查找的元素
	for (i = 0; i < len; i++)
	{
		if (arr[i] == n)
		{
			printf("%d的下标是%d\n", n, i);
			break;//找到后就直接跳出循环
		}
	}
	if (i == len)//因为如果数组元素全部遍历一遍后,都没有i++等于len后,便跳出循环再判断说不存在。
		printf("Don't have number %d\n", n);	
	return 0;
}

线性查找非常简单但,要是数组元素较大,就比较麻烦,毕竟要一个个遍历过去时间复杂度为n。

 

二分查找

来看看二分查找,就是高中数学学到过的二分法,原理相当简单。但是它只能查找已经排序好的数组,与线性查找相比,有些局限性。
通过比较数组中间数据与目标数据的大小,来判断是在中间数据的左边还是右边,瞬间缩小一半的运算量。再按照这种继续比较,直到找到或找不到为止。

#include <stdio.h>
int main(void)
{
	int n;
	scanf("%d", &n);
	int arr[] = { 1,2,3,4,5,6,7,8,9,10};
	int len = sizeof(arr) / sizeof(arr[0]);
	int left = 0;
	int right = len - 1;
	int mid;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (arr[mid] > n)
		{
			right = mid-1;
		}
		else if (arr[mid] < n)
		{
			left = mid+1;
		}
		else 
		{
			break;
		}
	}
	if (left <= right)
		printf("%d的下标是%d\n", n, mid);
	else 
		printf("DON't have number %d\n", n);
	return 0;
}
	/*int i = 1;

看张图吧,方便理解与记忆。

C语言编程之初识数组线性查找和二分查找

看代码中的,中间元素是5,在5的右边,再把不需要的元素移出比较范围,再,重新设置中间元素,进行比较。

C语言编程之初识数组线性查找和二分查找

再拿8进行比较,在8左边。重新规划范围。

C语言编程之初识数组线性查找和二分查找

7比6大,则在6右边,继续比较。

C语言编程之初识数组线性查找和二分查找

此时,left==right,跟据while循环条件,依旧可以进入循换,但arr[mid]7,说明已经找到那个元素,会break;跳出循环,再判断条件满足left<=right,说明依旧成立,就输出。
否则,如果目标元素是11,则一直会是中间元素的右边。

C语言编程之初识数组线性查找和二分查找

再left=MID+1就是10,此时,leftright,循环还没结束,这一次,mid等于10还是比11小,left=10+1,而此时,left>right,不符合条件,循环结束,再判断,不符合条件,就进入else,,说明,11不在数组内。
我第一次写二分查找时,没有写

left = mid+1;
right = mid-1;

而是写

right = mid;
left = mid;

本以为差不多,额,事实上确实差不多,不过当目标数据不在数组内时,要提前判断。如果直接以上面代码的形式,改条件,就会造成,left一直是9,right一直是10,mid也一直是9,无法跳出循环,造成这样的死循环局面。
当写二分查找时一定要切记。
这两个查护,目前就这些。
如有问题,烦请大佬指点一二。
谢谢观看。

以上就是C语言编程之初识数组线性查找和二分查找的详细内容,更多关于C语言数组的资料请关注服务器之家其它相关文章!

原文链接:https://blog.csdn.net/weixin_52199109/article/details/112726928

延伸 · 阅读

精彩推荐
  • C/C++c++ 单线程实现同时监听多个端口

    c++ 单线程实现同时监听多个端口

    这篇文章主要介绍了c++ 单线程实现同时监听多个端口的方法,帮助大家更好的理解和学习使用c++,感兴趣的朋友可以了解下...

    源之缘11542021-10-27
  • C/C++C/C++经典实例之模拟计算器示例代码

    C/C++经典实例之模拟计算器示例代码

    最近在看到的一个需求,本以为比较简单,但花了不少时间,所以下面这篇文章主要给大家介绍了关于C/C++经典实例之模拟计算器的相关资料,文中通过示...

    jia150610152021-06-07
  • C/C++详解c语言中的 strcpy和strncpy字符串函数使用

    详解c语言中的 strcpy和strncpy字符串函数使用

    strcpy 和strcnpy函数是字符串复制函数。接下来通过本文给大家介绍c语言中的strcpy和strncpy字符串函数使用,感兴趣的朋友跟随小编要求看看吧...

    spring-go5642021-07-02
  • C/C++C++之重载 重定义与重写用法详解

    C++之重载 重定义与重写用法详解

    这篇文章主要介绍了C++之重载 重定义与重写用法详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...

    青山的青6062022-01-04
  • C/C++C语言实现电脑关机程序

    C语言实现电脑关机程序

    这篇文章主要为大家详细介绍了C语言实现电脑关机程序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...

    xiaocaidayong8482021-08-20
  • C/C++学习C++编程的必备软件

    学习C++编程的必备软件

    本文给大家分享的是作者在学习使用C++进行编程的时候所用到的一些常用的软件,这里推荐给大家...

    谢恩铭10102021-05-08
  • C/C++C语言中炫酷的文件操作实例详解

    C语言中炫酷的文件操作实例详解

    内存中的数据都是暂时的,当程序结束时,它们都将丢失,为了永久性的保存大量的数据,C语言提供了对文件的操作,这篇文章主要给大家介绍了关于C语言中文件...

    针眼_6702022-01-24
  • C/C++深入理解goto语句的替代实现方式分析

    深入理解goto语句的替代实现方式分析

    本篇文章是对goto语句的替代实现方式进行了详细的分析介绍,需要的朋友参考下...

    C语言教程网7342020-12-03