C语言折半查找法的超详细讲解

折半查找法仅适用于对已有顺序的数组、数据进行操作！！！（从小到大）自我总结：折半查找法就是相当于（通过改变low或high的大小）把中间位置指到了key那个数那里，所以mid应该处于循环里面，即mid=（high+low）/2。注意：low，mid，high都要与下标绑定，也就是说它们就是下标。且循环条件是：high>=low.

同时注意：⑴若原来数组是由小到大排列的则：

      mid=(high+low)/2;
            if(key<a[mid])//说明要找的值在左边
            high=mid-1;
            else if(key>a[mid])//说明要找的值在mid右边
            low=mid+1;//最小值的位置往右进一位

㈡若原来数组是由大到小排列的则：

mid=(high+low)/2;
            if(key>a[mid])//注意是由大到小排列 ，所以此时key在a【mid】 左边，故high=mid-1 ；
            high=mid-1;
            else if(key<a[mid])//注意是由大到小排列，所以此时key在a【mid】右边，故low=mid+1；
            low=mid+1;

当然在下面这个代码中，也可以用选择排序法和冒泡法来对任意数组进行排序，然后在应用此函数，保证折半查找法的前提是排好序了。

#include<stdio.h>
 void zb(int key,int a[],int n)//key表示要找的数，a表示数组，n表示数组元素个数
 {
     int i,high,low,mid;
     int count1=0,count=0;
     low=0;
     high=n-1;
     while(high>=low)//保证右下标不小于左下标
     {
        count++;
        mid=(high+low)/2;//总的来说变得是中间位置相当于把中间位置移到了key那个数那里，所以mid应该处于循环里面
         if(key<a[mid])//说明key在a【mid】的左半边 ,那么最右边的high下标就可以在下标mid基础上往左进一个单位了
        high=mid-1;
         else if(key>a[mid])//说明key在a【mid】的右半边 ,那么最左边的low下标就可以在下标mid基础上往右进一个单位了
         low=mid+1;
        if(key==a[mid])
        {
            printf("元素找到了！！！\n一共查找了%d次\n它处于a[%d]位置上\na[%d]=%d\n",count,mid,mid,key);
            count1++;
            break;
        }
    }
     if(count1==0)
     printf("元素不存在！！！\n");
 }
 int main ()
 {
     int key,n,a[100];
     int i;
     void zb(int key,int a[],int n);//声明定义函数
     printf("请输入数组元素个数：\n");
     scanf("%d",&n);
     printf("请输入（从小到大）所有数组元素：\n");
     for(i=0;i<n;i++)
     {
         scanf("%d",&a[i]);
     }
     printf("请输入要查找的数：\n");
     scanf("%d",&key);
     zb(key,a,n);
     printf("\n");
     return 0;
 }

总结

到此这篇关于C语言折半查找法的文章就介绍到这了,更多相关C语言折半查找法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言算法练习之折半查找的实现

    C语言算法练习之折半查找的实现

    目录 1. 题目描述 2. 问题分析 3. 算法设计 4. 动图演示 5. 代码实现 6.知识点补充 continue 语句 break 语句 continue语句 和 break语句的区别 7. 问题拓展 1. 题目描述 N 个有序整数数列已放在一维数组中,利用二分查找法查找整数 m 在数组中的位置. 若找到,则输出其下标值:反之,则输出 “ Not be found!”. 2. 问题分析 二分查找法(也叫折半查找)其本质是分治算法的一种. 所谓分治算法是指的分而治之,即将较大规模的问题分解成

  • C语言实现顺序表的顺序查找和折半查找

    本文实例为大家分享了C语言实现顺序表的顺序查找和折半查找的具体代码,供大家参考,具体内容如下 顺序查找: #include <iostream> using namespace std; int SeqSearch(int r[],int n,int k) { r[0]=k;//下标0用作哨兵存放要查询的数 int i=n; while(r[i]!=k)//不用判断下标i是否越界 { i--; } return i; } int main() { int n; cout<<&quo

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

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

  • 纯C语言:折半查找源码分享

    复制代码 代码如下: #include <stdio.h>       int bin_search(int key[],int low, int high,int k)      {        int mid;        if(low>high)    {       return -1;        }    else       {             mid = (low+high) / 2;             if(key[mid]==k)         

  • C语言数据结构之 折半查找实例详解

    C语言数据结构之 折半查找实例详解

    数据结构 折半查找 实例代码: /* 名称:折半查找 语言:数据结构C语言版 编译环境:VC++ 6.0 日期: 2014-3-26 */ #include <stdio.h> #include <malloc.h> #include <windows.h> #define N 11 // 数据元素个数 typedef int KeyType; // 设关键字域为整型 typedef struct // 数据元素类型 { KeyType key; // 关键字域 int

  • C语言实现折半查找法（二分法）

    折半查找法也叫做二分查找,顾名思义,就是把数据分成两半,再判断所查找的key在哪一半中,再重复上述步骤知道找到目标key; 注意:折半查找法仅适用于对已有顺序的数组.数据进行操作!!! 很显然,折半查找法相对于其他查找方法例如顺序查找法效率要高很多: 下面我们来实际操作一下,了解二分查找的奥义. 例如:要在数组arr[]={8,7,9,6,4,1,2,5,3,10,11};中查找key=7的位置:首先,我们要先将数组arr中的数据成员进行排序.arr[]={1,2,3,4,5,6,7,8,9,1

  • C语言折半查找法的超详细讲解

    折半查找法仅适用于对已有顺序的数组.数据进行操作!!!(从小到大)自我总结:折半查找法就是相当于(通过改变low或high的大小)把中间位置指到了key那个数那里,所以mid应该处于循环里面,即mid=(high+low)/2.注意:low,mid,high都要与下标绑定,也就是说它们就是下标.且循环条件是:high>=low. 同时注意:⑴若原来数组是由小到大排列的则:       mid=(high+low)/2;             if(key<a[mid])//说明要找的值在左边

  • C语言折半查找法介绍及使用示例

    C语言折半查找法介绍及使用示例

    目录 1. 折半查找介绍 1.1 定义 1.2 基本原理 1.3 时间复杂度与空间复杂度 1.4 优缺点 2. 代码实现 2.1 代码设计 2.2 代码实现 1. 折半查找介绍 1.1 定义 折半查找也称二分查找,是一种在有序数组中查找某一特定元素的搜索算法,每一次查找,搜索范围均缩小一半,效率较高.如果数组是乱序状态,则应排序,再进行查找. 1.2 基本原理 搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束:如果某一特定元素大于或者小于中间元素,则在数组大于或小于中

  • C语言折半查找法的由来及使用详解

    C语言折半查找法的由来及使用详解

    目录 引入二分查找 分析二分查找 计算中间下标的两种方法 第一种 第二种 代码实现 总结 引入二分查找 本文带着大家学习一个简单的**二分查找算法,也叫折半查找算法** 先给大家提出一个问题 额,大家应该都会碰到这种情况,那大家怎么猜呢? 我想一定是会说1000,他说太少了,你又猜1500… 这其实就是二分查找的应用. 接下来我们来看一个问题 如何在一个有序数组中查找一个数字? 有一部分帅气的观众可能会说: 直接遍历数组,一个一个对比就找到了啊 但是大家有没有想过一个问题,数组中如果只有几十个数

  • C语言哈希表概念超详细讲解

    目录 1. 哈希概念 2. 哈希冲突 3. 哈希实现 3.1 闭散列(哈希表) 3.1.1 闭散列的细节 3.1.2 优化后的闭散列 3.2 扩散列(哈希桶) 3.2.1 扩散列的细节 4. 哈希表和哈希桶的比较 5. 结尾语 1. 哈希概念 哈希其实在学排序时已经用过了,就是计数排序.计数排序也是用的一种映射关系. 比如对此数组进行 计数排序 :1 1 9 9 9 3 3 8 8 我用的是绝对映射 ,所以开辟的数组空间 它的大小 必须 能映射到 最大的元素. 但是 对于哈希来讲,可以用决定映射

  • C语言 超详细讲解算法的时间复杂度和空间复杂度

    C语言 超详细讲解算法的时间复杂度和空间复杂度

    目录 1.前言 1.1 什么是数据结构? 1.2 什么是算法? 2.算法效率 2.1 如何衡量一个算法的好坏 2.2 算法的复杂度 2.3 复杂度在校招中的考察 3.时间复杂度 3.1 时间复杂度的概念 3.2 大O的渐进表示法 3.3 常见时间复杂度计算举例 4.空间复杂度 5. 常见复杂度对比 1.前言 1.1 什么是数据结构? 数据结构(Data Structure)是计算机存储.组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合. 1.2 什么是算法? 算法(Algorit

  • C语言超详细讲解数据结构中双向带头循环链表

    C语言超详细讲解数据结构中双向带头循环链表

    目录 一.概念 二.必备工作 2.1.创建双向链表结构 2.2.初始化链表 2.3.动态申请节点 2.4.打印链表 2.5.销毁链表 三.主要功能 3.1.在pos节点前插入数据 尾插 头插 3.2.删除pos处节点数据 尾删 头删 3.3.查找数据 四.总代码 List.h 文件 List.c 文件 Test.c 文件 五.拓展 一.概念 前文我们已经学习了单向链表,并通过oj题目深入了解了带头节点的链表以及带环链表,来画张图总体回顾下: 在我们学习的链表中,其实总共有8种,都是单双向和带不带

  • C语言数据结构超详细讲解单向链表

    C语言数据结构超详细讲解单向链表

    目录 1.链表概况 1.1 链表的概念及结构 1.2 链表的分类 2. 单向链表的实现 2.1 SList.h(头文件的汇总,函数的声明) 2.2 SList.c(函数的具体实现逻辑) 2.2.1 打印链表 2.2.2 搞出一个新节点(为其他函数服务) 2.2.3 链表尾插 2.2.4 链表头插 2.2.5 链表尾删 2.2.6 链表头删 2.2.7 查找节点 2.2.8 在pos位置之前插入 2.2.9 在pos位置之后插入 2.2.10 删除pos位置 2.2.11 删除pos之后位置 2.

  • C语言超详细讲解轮转数组

    C语言超详细讲解轮转数组

    目录 题目描述 实例 解题思路 1. 先整体逆转 2.逆转子数组[0, k - 1] 3.逆转子数组[k, numsSize - 1] 易错点 代码 题目描述 给你一个数组,将数组中的元素向右轮转 k 个位置,其中 k 是非负数.OJ链接 实例 1.实例1 输入: nums = [1,2,3,4,5,6,7], k = 3输出: [5,6,7,1,2,3,4]解释:向右轮转 1 步: [7,1,2,3,4,5,6]向右轮转 2 步: [6,7,1,2,3,4,5]向右轮转 3 步: [5,6,7

  • C语言操作符超详细讲解下篇

    C语言操作符超详细讲解下篇

    目录 前言 赋值操作符 单目操作符 单目操作符介绍 sizeof 和 数组 关系操作符 逻辑操作符 条件操作符 逗号表达式 下标引用与函数调用和结构成员 [ ] 下标引用操作符 ( ) 函数调用操作符 访问一个结构的成员 表达式求值 隐式类型转换-整形提升 算术转换 操作符的属性 总结 前言 本文接着学习操作符的内容. 赋值操作符 赋值操作符就是能够重新赋值 int weight = 120;//体重 weight = 89;//不满意就赋值 double salary = 10000.0; s

随机推荐