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,10,11};
如图所示:将该组数据小端记作low,大端记作high,中间值记作mid;
二分法查找时,将所查找的key与mid比较,例如key=7,即可缩小查找范围在mid和high之间;
如图所示即可找到key=low=7;
注意: (敲黑板)如果中间数mid不是整数,需要进行取整。
代码如下:
#include<stdio.h> int BinSearch(int arr[],int len,int key) //折半查找法(二分法) { int low=0; //定义初始最小 int high=len-1; //定义初始最大 int mid; //定义中间值 while(low<=high) { mid=(low+high)/2; //找中间值 if(key==arr[mid]) //判断min与key是否2020111122411718相等 return mid; else if(key>arr[mid]) //如果key>mid 则新区间为[mid+1,high] low=mid+1; else //如果key<mid 则新区间为[low,mid-1] high=mid-1; } return -1; //如果数组中无目标值key,则返回 -1 ; } int main() { int arr[]={1,2,3,4,5,6,7,8,9,10,11}; //首先要对数组arr进行排序 printf("%d \n",BinSearch(arr,(sizeof(arr)/sizeof(arr[0])),7)); return 0; }
运行结果如下:
希望对您有所帮助!
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。
相关推荐
-
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语言:折半查找源码分享
复制代码 代码如下: #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语言版 编译环境: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语言二分法求解方程根的两种方法
本文实例为大家分享了C语言二分法求解方程根的具体代码,供大家参考,具体内容如下 对于二分法求根,其实和弦截法思想很像,甚至更简单. 原理:先看如下的图 A,B两个点为跟的一个边界,通过一直缩小跟的边界,从而获取跟的值. (1)知道函数(即方程的式子),这个好说,题上都有 (2)循环的输入A,B的横坐标的值,即x1,x2的初值,直到f(x1)与f(x2)的乘积为负数才停止.(必须保证方程的跟在(x1,x2)区间)这样的x1,x2的初值才有意义. (3)令xx=(x1+x2)/2;(即中值),若f(
-
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语言折半查找法介绍及使用示例
目录 1. 折半查找介绍 1.1 定义 1.2 基本原理 1.3 时间复杂度与空间复杂度 1.4 优缺点 2. 代码实现 2.1 代码设计 2.2 代码实现 1. 折半查找介绍 1.1 定义 折半查找也称二分查找,是一种在有序数组中查找某一特定元素的搜索算法,每一次查找,搜索范围均缩小一半,效率较高.如果数组是乱序状态,则应排序,再进行查找. 1.2 基本原理 搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束:如果某一特定元素大于或者小于中间元素,则在数组大于或小于中
-
C语言折半查找法的由来及使用详解
目录 引入二分查找 分析二分查找 计算中间下标的两种方法 第一种 第二种 代码实现 总结 引入二分查找 本文带着大家学习一个简单的**二分查找算法,也叫折半查找算法** 先给大家提出一个问题 额,大家应该都会碰到这种情况,那大家怎么猜呢? 我想一定是会说1000,他说太少了,你又猜1500… 这其实就是二分查找的应用. 接下来我们来看一个问题 如何在一个有序数组中查找一个数字? 有一部分帅气的观众可能会说: 直接遍历数组,一个一个对比就找到了啊 但是大家有没有想过一个问题,数组中如果只有几十个数
-
Java利用泛型实现折半查找法
目录 泛型化的折半查找法 1.题目 2.解题思路 3.代码详解 知识点补充 泛型化的折半查找法 1.题目 泛型是JAVA重要的特性,使用泛型编程,可以使代码复用率提高. 实现:查找作为泛型的一个简单应用,使用泛型实现折半查找法 2.解题思路 创建一个类:BinSearch. 折半查找要求数据集合中的元素必须可比较,并且各元素按升序或降序排列.取集合的中间元素作为比较对象,如: (1)如果给定的值与比较对象相等,则查找成功,返回中间元素的序号. (2)如果给定的值大于比较对象,则在中间元素的右半段
-
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 <
-
Python 语言实现六大查找算法
目录 一.顺序查找算法 二.折半查找算法 三.插补查找算法 四.哈希查找算法 五.分块查找算法 六.斐波那契查找算法 七.六种查找算法的时间复杂度 一.顺序查找算法 顺序查找又称为线性查找,是最简单的查找算法.这种算法就是按照数据的顺序一项一项逐个查找,所以不管数据顺序如何,都得从头到尾地遍历一次.顺序查找的优点就是数据在查找前,不需要对其进行任何处理(包括排序).缺点是查找速度慢,如果数据列的第一个数据就是想要查找的数据,则该算法查找速度为最快,只需查找一次即可:如果查找的数据是数据列的最后一
-
用C语言实现二分查找算法
目录 一.前言 二.二分查找法 1.什么是二分查找法 2.如何用c语言来实现二分查找法 三.总结 总结 一.前言 假如今天我们需要在一个有序的数组中来寻找一个数的下标,就用"1,2,3,4,5,6,7,8,9"这九个数组成的数组来说,假如我们想寻找'2',那很简单我们只用从小到大开始寻找,寻找两次就完成了,但是我们想寻找'7',我们继续用从小到大挨个寻找,这就显得有点慢并且耗时长还没有效率,因此我们可以有一种全新的方法,二分查找法来解决这个问题. 二.二分查找法 1.什么是二分查找法
-
java数据结构之二分查找法 binarySearch的实例
java数据结构之二分查找法 binarySearch的实例 折半查找法,前提是已经排好序的数组才可查找 实例代码: public class BinarySearch { int[] bArr; public void setArr(int[] bArr){ this.bArr=bArr; } public static void main(String[] args) { int arrLength=16; int[] bArr=new int[arrLength]; System.out.
-
javascript折半查找详解
折半查找法: 在有序表中,把待查找数据值与查找范围的中间元素值进行比较,会有三种情况出现: 1) 待查找数据值与中间元素值正好相等,则放回中间元素值的索引. 2) 待查找数据值比中间元素值小,则以整个查找范围的前半部分作为新的查找范围,执行1),直到找到相等的值. 3) 待查找数据值比中间元素值大,则以整个查找范围的后半部分作为新的查找范围,执行1),直到找到相等的值 4) 如果最后找不到相等的值,则返回错误提示信息. 按照二叉树来理解:中间值为二叉树的根,前半部
随机推荐
- SQLserver排序规则基本概念探索
- Mootools 1.2教程(3) 数组使用简介
- AngularJS 应用身份认证的技巧总结
- jquery scrollTop方法根据滚动像素显示隐藏顶部导航条
- 用javascript做一个webgame连连看大家看下
- PHP面向对象之后期静态绑定功能介绍
- python解决网站的反爬虫策略总结
- jsp实现cookie的使用
- C#影院售票系统毕业设计(1)
- Android开发之自定义刮刮卡实现代码
- CentOS下将MySQL 5.1升级到MySQL 5.5的步骤
- Java多线程的实现方式比较(两种方式比较)
- JBuilder2005实战JSP之切换控制 图文步骤
- js内置对象处理_打印学生成绩单的简单实现
- MongoDB的主从复制及副本集的replSet配置教程
- PHP更新购物车数量(表单部分/PHP处理部分)
- 局域网中IP地址的设置
- 深入学习springboot线程池的使用和扩展
- Spring Security OAuth2认证授权示例详解
- centos中文件与权限的基本操作教程