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;
}

运行结果如下：

希望对您有所帮助！

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (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语言数据结构之 折半查找实例详解

    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语言:折半查找源码分享

    复制代码 代码如下: #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语言实现折半查找法（二分法）

    折半查找法也叫做二分查找,顾名思义,就是把数据分成两半,再判断所查找的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… 这其实就是二分查找的应用. 接下来我们来看一个问题 如何在一个有序数组中查找一个数字? 有一部分帅气的观众可能会说: 直接遍历数组,一个一个对比就找到了啊 但是大家有没有想过一个问题,数组中如果只有几十个数

  • Java利用泛型实现折半查找法

    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 语言实现六大查找算法

    Python 语言实现六大查找算法

    目录 一.顺序查找算法 二.折半查找算法 三.插补查找算法 四.哈希查找算法 五.分块查找算法 六.斐波那契查找算法 七.六种查找算法的时间复杂度 一.顺序查找算法 顺序查找又称为线性查找,是最简单的查找算法.这种算法就是按照数据的顺序一项一项逐个查找,所以不管数据顺序如何,都得从头到尾地遍历一次.顺序查找的优点就是数据在查找前,不需要对其进行任何处理(包括排序).缺点是查找速度慢,如果数据列的第一个数据就是想要查找的数据,则该算法查找速度为最快,只需查找一次即可:如果查找的数据是数据列的最后一

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

    用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)     如果最后找不到相等的值,则返回错误提示信息. 按照二叉树来理解:中间值为二叉树的根,前半部

随机推荐