一篇文章带你了解C语言二分查找

目录
  • 总结

我们常常需要对数据进行查找，修改，查找数据有许多方法，我们先看看最简单的顺序查找

int main()
{
	int i, k = 0;
	scanf("%d", &k);
	int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	for (i = 0; i < sz; i++)
	{
		if (arr[i] == k)
		{
			printf("找到了，它是%d", arr[i]);
		}
	}
	return 0;
}

顺序查找绝大多数情况有效但是由于它是一个一个元素进行查找，其效率很低，只有一个for循环所有其时间复杂度为O（n）。我们希望有一个更高效的查找方法，接下来便是二分查找，先来看看一个顺序查找和二分查找的直观比较。

从上面的图中我们感受到二分查找的关键：找到最左边元素（low）和最右边元素（high），确定中间元素（mid），比较中间元素（mid）和目标元素（k）的大小，调整low和high，再确定新的mid....我们要不断确定mid直到找到k，自然需要用到循环，我们有明确的目标：找到k。因此选择while循环，找到k后循环不再进行，而当low和high之间还有元素，即low在high的左边或与之重合，k就依然可能存在，所以循环条件为low<=high，接下来的问题在于怎样调整low和high的值，mid和k比较无非就三种情况：mid<k，mid>k,mid=k。第一种情况，k在mid的右边，我们将low调整为mid+1，high不用调整；第二种情况，k在mid的左边，我们将high调整为mid-1，low不用调整。最后一种情况最简单，我们已经找到了k，直接将mid打印出来就行了，代码如下：

#include <stdio.h>
int main()
{
	int k = 0;
	scanf("%d", &k);
	int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	int sz = sizeof(arr) / sizeof (arr[0]);
	int low = 0;
	int high = sz-1;
	while (low <= high)
	{
		int mid = (low + high) / 2;
		if (arr[mid] > k)
		{
			high = mid - 1;
		}
		else if (arr[mid] < k)
		{
			low = mid + 1;
		}
		else
		{
			printf("找到了，它是：%d", arr[a]);
			break;
		}
	}
	if (l>r)
		printf("没找到，请重新输入");
	return 0;
}

二分查找的时间复杂度的问题：总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。由于n/2^k取整后>=1，即令n/2^k=1，可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O(logn)，确实比顺序查找快不少，但是二分查找有一个较大的局限性:只能查找有序数组的元素，即组数字必须是升序或降序。

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容！

赞 (0)

相关推荐

  • C语言数据结构中二分查找递归非递归实现并分析

    C语言数据结构中二分查找递归非递归实现并分析

    C语言数据结构中二分查找递归非递归实现并分析 前言: 二分查找在有序数列的查找过程中算法复杂度低,并且效率很高.因此较为受我们追捧.其实二分查找算法,是一个很经典的算法.但是呢,又容易写错.因为总是考虑不全边界问题. 用非递归简单分析一下,在编写过程中,如果编写的是以下的代码: #include<iostream> #include<assert.h> using namespace std; int binaty_search(int* arr, size_t n, int x)

  • 一篇文章带你了解C语言二分查找的简单应用

    一篇文章带你了解C语言二分查找的简单应用

    目录 前言 实战演练 思路分析 总结 前言 在有序数组中查找具体的某个数字n,可能有同学会说一个一个找,但是这样的效率实在太低,特别是对于有序的数组,效率太低.我们一般从中间元素开始找,查一次去掉一半数字,这种方法我们给它取名为折半查找即为二分查找,效率大大提高!怎么理解呢?如果有2的32次方个数字,我们最多只需查找32次,而一个一个数运气不好却是2的32次方次. 实战演练 这里我们先给出所写代码以及运行结果 在这里,给大家分析一下,首先,我们先创建一个有序数组arr[],然后我们把要查找的7用

  • C语言算法--有序查找(折半查找/二分查找)

    目录 题目 解法一: 挨个遍历 方法二:折半查找/二分查找(仅适用于有序查找) 总结 题目 首先我们来把题目瞅一眼: 在一个有序数组中查找具体的某个数字n. 编写int binary_search (int x, int v[], int n); 功能:在v [0] <= v [1] <= v [2] <= -. <= v [n-1]的数组中查找x. 题目大概的意思就是说这是一串有序的数组,我们编写代码完成以下功能:如果输入的数字在数组中,就输出找到了并输出下标,如果输入的数字不在

  • C语言基础之二分查找知识最全汇总

    C语言基础之二分查找知识最全汇总

    一.前言 在自学二分查找的过程中我想到了一些变化问题,有的自己就慢慢理解了,有的在网上找到了答案,奈何没有找到想要的总结归纳.我就斗胆自己写了一篇,号称史上最全.希望和我一样的伙伴可以少走一点弯路. 二分查找凭借其低时间复杂度O(log(n))成为了各个蒟蒻的入门知识,但是其衍生出的各种题目相较原题目而言就没有那么容易求解,以下借用c语言实现二分查找算法及其衍生.二分查找仅适用于事先已经排好序的顺序表.其基本思路就是每次取中间数,如果中间数大于所求数就向上查找,反之向下. 二.原始二分查找 1.

  • C语言快速排序与二分查找算法示例

    本文实例讲述了C语言二分排序与查找算法.分享给大家供大家参考,具体如下: 题目:首先产生随机数,再进行快速排序,再进行二分查找. 实现代码: #include <stdio.h> #include <stdlib.h> #include <time.h> void quiksort(int a[],int low,int high) { int i = low; int j = high; int temp = a[i]; if( low < high) { wh

  • 一篇文章带你了解C语言二分查找

    一篇文章带你了解C语言二分查找

    目录 总结 我们常常需要对数据进行查找,修改,查找数据有许多方法,我们先看看最简单的顺序查找 int main() { int i, k = 0; scanf("%d", &k); int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int sz = sizeof(arr) / sizeof(arr[0]); for (i = 0; i < sz; i++) { if (arr[i] == k) { printf("

  • 一篇文章带你入门C语言:函数

    一篇文章带你入门C语言:函数

    目录 函数 定义 库函数 定义 介绍 Example 1 strcpy Example 2 memset 自定义函数 Example 1 Example 2 两数交换 链式访问 Example 1 函数声明 函数递归 Example 1 Example 2 函数迭代 Example 3 Example 4 总结 函数 定义 程序里的函数又被叫做子程序,他作为一个大型程序的部分代码,有一或多个语句项组成.函数负责完成某项特定任务,提供了对过程的封装和对细节的隐藏,这样的代码通常会被集成为软件库.

  • 一篇文章带你入门C语言:操作符

    一篇文章带你入门C语言:操作符

    目录 操作符 分类 算术操作符 移位操作符 整数存储规则 左右移位规则 赋值操作符 单目操作符 取地址操作符& 解引用操作符* 类型长度操作符sizeof 按位取反操作符~ ++ -- 操作符 强制类型转换操作符(type) 关系操作符= 逻辑操作符 短路运算 条件操作符 逗号表达式 下标引用.函数调用和结构成员 下标引用操作符[] 函数调用操作符() 结构成员操作符. -> 结构体定义 结构体使用 结构体地址 表达式求值 隐式类型转换 整型提升 如何整型提升 有符号数 无符号数 算术转换

  • 一篇文章带你了解C语言:入门基础(2)

    一篇文章带你了解C语言:入门基础(2)

    目录 操作符 算术操作符 移位操作符 位操作符 单目操作符 逻辑反操作! 操作符++,-- 逻辑操作符 条件操作符 逗号表达式 常见关键字 typedef extern static 修饰局部变量 修饰全局变量和函数 其它 #define定义常量和宏 定义常量 定义宏 指针 内存单元 指针变量 &取地址操作符,*解引用操作符 类型所占空间 结构体 定义结构体 使用结构体变量 总结 本节将结束对初识C语言的概述,只追求大概,不求精细. 本节包括的内容有操作符,常见关键字,#define定义常量和宏

  • 一篇文章带你了解C语言--数据的储存

    一篇文章带你了解C语言--数据的储存

    目录 前言 数据类型介绍 类型的基本归类 整形在内存中的存储 原码.反码.补码 大小端介绍 浮点型在内存中的存储 前言 前面我们学习了C语言的一些基本知识和基础的语法,想必大家对C语言都有了自己的认识. 当然只是学习这些知识还是不够的,我们需要进行更加深入的学习. 从本章开始,我们将进行C语言进阶阶段的学习,所以难度会有所增加. 数据类型介绍 前面我们已经学习了基本的内置类型: char //字符数据类型 short //短整型 int //整形 long //长整型 long long //更

  • 一篇文章带你了解C语言浮点数之间的比较规则

    一篇文章带你了解C语言浮点数之间的比较规则

    目录 你认为这段代码输出什么? 为什么不等于呢? 应该怎么解决? 那么怎么判断两个浮点数 f1 和 f2 相等呢. 伪代码 可以简化为 >> 怎么判断浮点数等于0? 还有一个问题 总结 你认为这段代码输出什么? int main() { float f1 = 1.1; float f2 = 2.2; if (f2 - 1.1 == f1) printf("等于"); else printf("不等于"); return 0; } 答案是不等于. 为什么不

  • 一篇文章带你入门C语言数据结构:绪论

    一篇文章带你入门C语言数据结构:绪论

    目录 绪论 什么是数据结构? Example 1 讨论 Example 2 Example 3 Example 4 总结 绪论 什么是数据结构? 不同于计算机操作培训,注意与程序设计的区别. Example 1 求n个数的最大值.次最大值. //1.遍历 - 最朴素的方法 int main() { int arr[10] = { 22,334,552,1,4,6,78,23,55,98 }; int i = 0; int temp = 0; int max1 = arr[0]; int max2

  • 一篇文章带你了解C语言:入门基础

    一篇文章带你了解C语言:入门基础

    目录 C语言本身特点 数据类型 常量变量 变量分类 使用小建议 生命周期作用域 常量分类及其特点 字符串+转义字符+注释 字符串 转义字符 两种注释 选择循环语句 函数 数组 总结 闲话少说,先上思维导图. 如图所示,现在还是初识C语言的第一部分,本次只介绍了C语言本身特点,数据类型,常量变量,字符串转义字符注释,选择循环语句,函数,数组. 接下来请和我一起粗略地探讨其中内涵所在. C语言本身特点 这是C语言的定义: C语言是一门通用计算机编程语言,广泛应用于底层开发.C语言的设计目标是提供一种

  • 一篇文章带你使用C语言编写内核

    一篇文章带你使用C语言编写内核

    目录 gcc 命令 文件头 将内核载入内存 总结 gcc 命令 使用 gcc 编译 c语言 -c 编译.汇编到目标代码,不进行链接,也就是直接生成目标文件 -o 将输出的文件以指定文件名来储存,有同名文件存在时直接覆盖 gcc -c -o kernel/main.o kernel/main.c 编译:编译号之后只是个目标文件,也称为待重定位文件,重定位指的是文件里面所用的符号还没有安排地址,这些符号的地址需要将来与其他目标文件"组成"一个可执行文件时再重新定位(编排地址〉,这里的符号就

随机推荐