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;

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

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

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

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

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

再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语言数组的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C语言编程之预处理过程与define及条件编译

    C语言编程之预处理过程与define及条件编译

    目录 名示常量#define 重定义常量 在#define中使用参数 预处理器粘合剂:##运算符 变参宏:- 和_ _ VAG_ARGS_ _ 宏与函数 预处理指令 #undef指令 从C预处理器的角度看已定义 条件编译 offsetof函数 这张图描述了从源文件到可执行文件的整体步骤 这张图展示了大体上步骤. 从代码到运行环境,编译器提供了翻译环境.在一个程序中,会存在多个文件 ,而每个源文件都会单独经过编译器处理. 预编译: 1,会将#include等头文件所包含的内容,库函数全部拷贝过来

  • C语言编程递归算法实现汉诺塔

    C语言编程递归算法实现汉诺塔

    汉诺塔 法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针.印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔.不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面.僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔.庙宇和众生也都将同归于尽. 这个传说挺有意思的,这个传说

  • C语言编程gcc如何生成静态库.a和动态库.so示例详解

    C语言编程gcc如何生成静态库.a和动态库.so示例详解

    目录 一.什么是静态库和动态库 二.gcc生成.a静态库和.so动态库 1.生成静态库(.a) 1.1编辑生成例子程序hello.h.hello.c和main.c 1.2将hello.c编译成.o文件 1.3由.o文件创建静态库 1.4在程序中使用静态库 1.5验证静态库的特点 2.生成动态库(.so) 2.1由.o文件创建动态库文件 2.2在程序中使用动态库 三.实例 1.实例1 1.1代码 1.2 静态库.a文件的生成与使用 1.3 动态库.so文件的生成与使用 2.实例2 2.1代码 2.

  • C语言编程之扫雷小游戏空白展开算法优化

    C语言编程之扫雷小游戏空白展开算法优化

    目录 写代码前,扫雷需要什么 进行主函数文件的代码 game文件以及函数步骤 在主函数文件中使用game函数 布值棋盘(雷盘和玩家棋盘) 打印棋盘函数 玩家排雷 计算雷数的函数 空白递归算法 写代码前,扫雷需要什么 1,游戏需要初始选择菜单 2,需要布置两个棋盘,一个布置雷,一个展示给玩家看 3,打印棋盘 4,玩家要输入选择的坐标,并且可以多次输入游戏坐标 5,每次输入后打印棋盘,同时判断是否继续还是输赢. 6,玩家每次输入坐标,都进行一次递归展开. 进行主函数文件的代码 void option

  • C语言编程计算信噪比SNR理解学习

    C语言编程计算信噪比SNR理解学习

    目录 概念 计算方法 相关认知 Taprint中的信噪比 实例 概念 这里面的信号指的是来自设备外部需要通过这台设备进行处理的电子信号,噪声是指经过该设备后产生的原信号中并不存在的无规则的额外信号(或信息),并且该种信号并不随原信号的变化而变化. 计算方法 信噪比的计量单位是dB,其计算方法是10lg(Ps/Pn),其中Ps和Pn分别代表信号与噪声的有效功率,也可以换算成电压幅值的比率关系:20Lg(Vs/Vn),Vs和Vn分别代表信号和噪声电压的"有效值". 在音频放大器中,我们希望

  • PTA刷题C语言编程顺序颠倒输出实现

    PTA刷题C语言编程顺序颠倒输出实现

    目录 这道题,是我遇见对数组元素的掌握与使用较为灵活的题目. 下面代码是我刚接触C++,刚学完类的一系列知识,连入门都没过,对C++的强大还未有多大认知,还是极具C语言的风格. 我看过一篇用C++完成的比这个简单多了. C语言也可以用栈来完成,虽然我有栈的实现函数,但我不愿去搞,就这样吧,实现也是对自己知识点掌握的加深认知. #include <iostream> #include <cstring> int main(void) { int a = 0; char ch; cha

  • C语言编程中常见的五种错误及对应解决方案

    目录 1. 未初始化的变量 2. 数组越界 3. 字符串溢出 4. 重复释放内存 5. 使用无效的文件指针 前言: C 语言有时名声不太好,因为它不像近期的编程语言(比如 Rust)那样具有内存安全性.但是通过额外的代码,一些最常见和严重的 C 语言错误是可以避免的. 即使是最好的程序员也无法完全避免错误.这些错误可能会引入安全漏洞.导致程序崩溃或产生意外操作,具体影响要取决于程序的运行逻辑. 下文讲解了可能影响应用程序的五个错误以及避免它们的方法: 1. 未初始化的变量 程序启动时,系统会为其

  • C语言如何与ARM汇编语言混合编程示例详解

    C语言如何与ARM汇编语言混合编程示例详解

    目录 一.ARM汇编语言简介 二.C语言调用汇编语言 1.无参数调用 2.有参数调用 三.汇编语言调用C语言 四.总结 五.参考文献 主要使用软件:keiL μVision5 一.ARM汇编语言简介 什么是汇编语言?汇编语言是任何一种适用于电子计算机.微处理器或其他可编程器件的低级语言.虽然被称为"低级语言",但是并不是说汇编语言真的"低级".特定的汇编语言和特定的机器语言指令集是一一对应的,不同平台之间不可直接移植.汇编语言主要包括传送指令.逻辑运算.移位指令.位

  • C语言编程之三个方法实现strlen函数

    C语言编程之三个方法实现strlen函数

    strlen()函数是来源于库函数<string.h> 是用于计算字符串的长度, 且字符串需要以'\0'结尾 strlen()会计算'\0'前的字符个数. 根据MSDN的描述 size_t strlen(const char* string); size_t==unsigned int; 返回-无符号整型. 现在提供三种方法实现strlen() 一.计数器法 我们是计算字符个数,可以设置一个变量,每找到一个字符,计数器就加一. int my_strlen(const char* arr)//计

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

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

    目录 线性查找 二分查找 先来了解一下什么是查找, 额,好吧,这没什么可了解的, 就是查找数组中的某个元素的位置或是否存在. 就这,没了.直接了解查找算法吧. 线性查找 线性查找与二分查找有些差别. 数组内元素可以是混乱无序的,即没有按顺序储存.这方法很简单,就是从首元素开始,依此向后查找,比较.仅此而已.运用循环,依次对比. 看代码吧. #include <stdio.h> int main(void) { int arr[] = { 5,4,6,8,7,9,10,2,3,1 }; int

  • C语言编程C++柔性数组结构示例讲解

    C语言编程C++柔性数组结构示例讲解

    目录 绕指柔-柔性数组 柔性数组的特点: 第一个好处是:方便内存释放 第二个好处是:这样有利于访问速度 总结 绕指柔-柔性数组 也许你从来没有听说过柔性数组(flexible array)这个概念,但是它确实是存在的. C99 中,结构体中的最后一个元素允许是未知大小的数组,这就叫做柔性数组成员. 柔性数组的特点: 1.结构中的柔性数组成员前面必须至少一个其他成员. 2.sizeof 返回的这种结构大小不包括柔性数组的内存. 3.包含柔性数组成员的结构用malloc ()函数进行内存的动态分配,

  • PHP有序表查找之二分查找（折半查找）算法示例

    本文实例讲述了PHP有序表查找之二分查找(折半查找)算法.分享给大家供大家参考,具体如下: 简介: 二分查找技术,又称为折半查找.它的前提是线性表中的记录必须是关键码有序(通常从小到达有序),线性表必须采用顺序存储. 基本思想: 在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功:若给定值小于中间记录的关键字,则在中间记录的左半区继续查找:若给定值大于中间记录的关键字,则在中间记录的右半区继续查找.不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败为止.

  • php顺序查找和二分查找示例

    复制代码 代码如下: <?php class search{ // 查找的源数组 private $array = array(1,2,3,5,7,6,4,8); /**  * 顺序查找法  * @param $val 要查找的值  */ public function query_search($val) {  foreach ($this->array as $k => $v)  {   if($v == $val)   {    echo '顺序查找成功!';    exit(0)

  • JavaScript折半查找（二分查找）算法原理与实现方法示例

    JavaScript折半查找（二分查找）算法原理与实现方法示例

    本文实例讲述了JavaScript折半查找(二分查找)算法原理与实现方法.分享给大家供大家参考,具体如下: 一.问题描述: 在一个升序数组中,使用折半查找得到要查询的值的索引位置.如: var a=[1,2,3,4,5,6,7,8,9]; search(a,3);//返回2 search(a,1);//左边界,返回0 search(a,9);//右边界,返回8 search(a,0);//比最小的值还小,返回"您查找的数值不存在" search(a,10);//比最大的值还大,返回&q

  • Java实现的两种常见简单查找算法示例【快速查找与二分查找】

    本文实例讲述了Java实现的两种常见简单查找算法.分享给大家供大家参考,具体如下: 前言: 查找是指从一批记录当中找出满足制定条件的某一记录的过程. 在平常的程序的编写当中很多时候时用得上的,这里简单介绍两个查找算法 1. 快速查找: 这个是相当简单的,以数组举例,就用一个for循环去查找数组中需要查找的数据 例子: public static boolean quickSearch(int a[], int x) { boolean f = false; int length = a.leng

  • 浅析C语言编程中的数组越界问题

    浅析C语言编程中的数组越界问题

    因为C语言不检查数组越界,而数组又是我们经常用的数据结构之一,所以程序中经常会遇到数组越界的情况,并且后果轻者读写数据不对,重者程序crash.下面我们来分析一下数组越界的情况: 1) 堆中的数组越界 因为堆是我们自己分配的,如果越界,那么会把堆中其他空间的数据给写掉,或读取了其他空间的数据,这样就会导致其他变量的数据变得不对,如果是一个指针的话,那么有可能会引起crash 2) 栈中的数组越界 因为栈是向下增长的,在进入一个函数之前,会先把参数和下一步要执行的指令地址(通过call实现)压栈,

  • java 折半查找法(二分查找)实例

    复制代码 代码如下: public class HalfSearch { public static int halfSearch(int a[], int x) {  int mid, left, right;  left = 0;  right = a.length - 1;   mid = (left + right) / 2;  while (a[mid] != x) {   if (x > a[mid]) {    left = mid + 1;   }   else if (x <

  • C语言编程中实现二分查找的简单入门实例

    架设有一个数组 v 已经按升序排列了,数组 v 有 n=20 个元素.数组中有个元素 x,如何知道 x 位于该数组的第几位呢? 解决这个问题的一个普遍方法就是二分查找法.下面是程序: #include <stdio.h> int binsearch(int x, int v[], int n); main() { int i, result, n; int wait; int x = 17; // 需要查找的数值 int v[19]; // 定义一个数组 // 给数组赋值 for(i = 0;

  • 用C语言实现二分查找算法

    用C语言实现二分查找算法

    目录 一.前言 二.二分查找法 1.什么是二分查找法 2.如何用c语言来实现二分查找法 三.总结 总结 一.前言 假如今天我们需要在一个有序的数组中来寻找一个数的下标,就用"1,2,3,4,5,6,7,8,9"这九个数组成的数组来说,假如我们想寻找'2',那很简单我们只用从小到大开始寻找,寻找两次就完成了,但是我们想寻找'7',我们继续用从小到大挨个寻找,这就显得有点慢并且耗时长还没有效率,因此我们可以有一种全新的方法,二分查找法来解决这个问题. 二.二分查找法 1.什么是二分查找法

随机推荐