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

目录
  • 前言
  • 实战演练
  • 思路分析
  • 总结

前言

在有序数组中查找具体的某个数字n，可能有同学会说一个一个找，但是这样的效率实在太低，特别是对于有序的数组，效率太低。我们一般从中间元素开始找，查一次去掉一半数字，这种方法我们给它取名为折半查找即为二分查找，效率大大提高！怎么理解呢？如果有2的32次方个数字，我们最多只需查找32次，而一个一个数运气不好却是2的32次方次。

实战演练

这里我们先给出所写代码以及运行结果

在这里，给大家分析一下，首先，我们先创建一个有序数组arr[],然后我们把要查找的7用int k表示，我们要确定这组数组的左下标0，右下标为sz-1，sz为数组的元素个数，即int left = 0,int right = sz-1;我们还要计算一下数组的元素总个数int sz =sizeof(arr)/sizeof(arr[0]);然后我们还需找出平均值int mid,如果arr[mid] < k,此时左下标left = mid+1，当arr[mid] > k,右下标right = mid-1,最后只剩一种情况直接打印break;出我们要求的mid，但是这只是一次查找，但是真正的二分查找需要好多次，那我们就需要让它循环while起来，需要一个条件left<=right,这说明中间还有元素，直到我们找到，但是当left>right时，此时我们可以大胆说明找不到，具体的代码如上图所示，这便是整个过程。小伙伴们赶紧int main(),return 0;敲起来试一试吧。

在这里，我在介绍另一种方法，通过函数的调用实现我们的二分查法。

这里的思路主要跟上一种方法的思路差不多，在这里说明一下不能用0 == ret，虽然说0为假，非0为真，但是在这组数组中1的下标就是为0，在这里提醒一下各位，另外，千万不能不传sz，即不能把int sz放在函数那一块区域里求，这种写法是有问题的，什么问题呢？这里简单说明一下，问题在于此时求的sz不是10，而是1，为什么？数组arr传参，实际传递的不是数组的本身，仅仅传过去了数组首元素的地址，即为a的指针，实际上int a[]只是挂羊皮卖狗肉，本质上是指针，所以在函数不能在函数内部求，根本求不出元素个数，另外，在int a []不需要写数字大小，没有意义，希望大家能够理解，int a []并不会真正创建一个数组，大家一定要注意，未来如果我们遇到函数内部需要参数部分传过来元素个数，一定是在外部求好元素个数的，大家一定要多加注意，即在函数内部求元素个数是做不到的。

思路分析

最后，在这里总结一下思路，进行思路分析，二分查找是要求所查找数组的顺序必须是有序的，我们定义left为最左端的元素，right为最右端的元素，mid=（left+right)/2为数组的中间位置，然后用所查找的值的位置与mid所处的位置进行比较，如果比mid小，只需在数组的前半部分查找，如果比mid大，在数组的后半部分查找，以此类推，直到查到到所寻找的值不在该数组为止，这便是整体的思路。

总结

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

赞 (0)

相关推荐

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

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

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

  • 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语言算法--有序查找(折半查找/二分查找)

    目录 题目 解法一: 挨个遍历 方法二:折半查找/二分查找(仅适用于有序查找) 总结 题目 首先我们来把题目瞅一眼: 在一个有序数组中查找具体的某个数字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语言二分查找

    目录 总结 我们常常需要对数据进行查找,修改,查找数据有许多方法,我们先看看最简单的顺序查找 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语言二分查找的简单应用

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

  • 一篇文章带你使用Typescript封装一个Vue组件(简单易懂)

    一.搭建项目以及初始化配置 vue create ts_vue_btn 这里使用了vue CLI3自定义选择的服务,我选择了ts.stylus等工具.然后创建完项目之后,进入项目.使用快捷命令code .进入Vs code编辑器(如果没有code .,需要将编辑器的bin文件目录地址放到环境变量的path中).然后,我进入编辑器之后,进入设置工作区,随便设置一个参数,这里比如推荐设置字号,点下.这里是为了生成.vscode文件夹,里面有个json文件. 我们在开发项目的时候,项目文件夹内的文件很

  • 一篇文章带你入门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语言的设计目标是提供一种

随机推荐