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

目录
  • 1. 折半查找介绍
    • 1.1 定义
    • 1.2 基本原理
    • 1.3 时间复杂度与空间复杂度
    • 1.4 优缺点
  • 2. 代码实现
    • 2.1 代码设计
    • 2.2 代码实现

1. 折半查找介绍

1.1 定义

折半查找也称二分查找，是一种在有序数组中查找某一特定元素的搜索算法，每一次查找，搜索范围均缩小一半，效率较高。如果数组是乱序状态，则应排序，再进行查找。

1.2 基本原理

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半 。

1.3 时间复杂度与空间复杂度

总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/ 2 k 2^k 2k，一直到1，其中k就是循环的次数。

由于n/ 2 k 2 ^ k 2k取整后>=1，即令n/ 2 k 2^k 2k=1，可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O()=O(logn)。

二分查找只需要额外存储三个变量：最大值 ，最小值 和 中点，空间复杂度为常数 O(1)。

1.4 优缺点

优点：比较次数少，查找速度快，平均性能好。

缺点：要求待查表为有序表，且插入删除困难。

2. 代码实现

2.1 代码设计

  1. 输入需要查找的元素，我们输入的是38；left是有序数组最左端0，是最小值，right是有序数组最右端10，是最大值，mid为数组1/2位置，即array[5]；
  2. 38比array[5] = 19大，因此left等于原mid+1，即array[6] = 26，right不变；新mid为(left+right)/2 = （6+10）/2 = 8；
  3. 38比array[8] = 36大，因此left等于上一次mid+1，即array[9] = 38，right不变；新mid为(left+right)/2 = （9+10）/2 = 9；
  4. 38等于array[9]，mid与left重合， 查找成功，返回数组下标9.

2.2 代码实现

#include <stdio.h>
#include <string.h>
int binarySearch(int array[],int len,int target){
    int left = 0;
    int right = len - 1;
    while(left <= right){
        int mid = (right + left) / 2;
        if(array[mid] == target){
            return mid;
        } else if(array[mid] < target){
            left = mid + 1;
        } else if(array[mid] > target){
            right = mid - 1;
        }
    }
    return -1;
}
int main(void)
{
    int array[]={2,3,4,5,15,19,26,27,36,38,45};
    int key = 0,ret;
    printf("请输入需要查找的数字:");
    scanf("%d",&key);
    ret = binarySearch(array,sizeof(array)/sizeof(int),key);
    if(ret < 0)
        printf("查找失败\n");
    else
        printf("该数字为数组第%d个元素\n",ret+1);
    return 0;
}

运行结果：

请输入需要查找的数字:38

该数字为数组第10个元素

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

赞 (0)

相关推荐

  • 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语言算法练习之折半查找的实现

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

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

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

  • 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语言实现折半查找法（二分法）

    折半查找法也叫做二分查找,顾名思义,就是把数据分成两半,再判断所查找的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)如果给定的值大于比较对象,则在中间元素的右半段

  • C语言顺序查找算法介绍及示例

    C语言顺序查找算法介绍及示例

    目录 1. 顺序查找介绍 1.1 定义 1.2 基本原理 1.3 时间复杂度与空间复杂度 1.4 优缺点 2. 代码实现 2.1 代码设计 2.2 代码实现 1. 顺序查找介绍 1.1 定义 查找是指在指定数据组合中找出满足条件的元素个体.顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法. 顺序查找是最基础也是最简单的查找算法,在需要进行查找时,这是我们的首选方法,只有数据较多,结构复杂,耗时较多需要优化时,我们才会考虑使用其他查找方法. 1.2 基本原理 对于任意一个序列以及一个

  • C语言文件读写操作介绍与简单示例

    文件的打开函数fopen() 文件的打开操作表示将给用户指定的文件在内存分配一个FILE结构区,并将该结构的指针返回给用户程序,以后用户程序就可用此FILE指针来实现对指定文件的存取操作了.当使用打开函数时,必须给出文件名.文件操作方式(读.写或读写),如果该文件名不存在,就意味着建立(只对写文件而言,对读文件则出错),并将文件指针指向文件开头.若已有一个同名文件存在,则删除该文件,若无同名文件,则建立该文件,并将文件指针指向文件开头. fopen(char *filename,char *ty

  • R语言科学计数法介绍:digits和scipen设置方式

    控制R语言科学计算法显示有两个option: digitis和scipen.介绍的资料很少,而且有些是错误的.经过翻看R语言的帮助和做例子仔细琢磨,总结如下: 默认的设置是: getOption("digits") [1] 7 getOption("scipen") [1] 0 digits 有效数字字符的个数,默认是7, 范围是[1,22] scipen 科学计数显示的penalty,可以为正为负,默认是0 R输出数字时,使用普通数字表示的长度 <= 科学计

  • 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 <

随机推荐