文档章节

C语言折半查找

胡若晨
 胡若晨
发布于 2016/04/05 19:55
字数 530
阅读 44
收藏 2

/*************************************************************************
    > File Name: bin_search.c
    > Author:heathcliff 
    > Mail:--------------------- 
    > Created Time: 2016年04月05日 星期二 18时12分46秒
 ************************************************************************/
#include<stdio.h>
#define M 5

/*折半查找法*/
int bin_search(int A[],int n,int key)
{
    int low,high,mid;

    low = 0;
    high = n-1;

    while(low <= high){

        mid = (low + high)/2;

        if(A[mid] == key)
            return mid;
        else if(A[mid] < key)
            low = mid + 1;
        else 
            high = mid - 1;
    }
    /*查找失败*/
    return -1;
}

/*直接插入排序*/
int insert_sort(int A[],int n)
{
    int i,j,temp; //temp 保存中间值

    for(i = 1;i < n; i++){
        temp = A[i];
        j = i - 1;

        while(j >= 0 && temp < A[j]){ //找到插入位置
            A[j+1] = A[j];

            j -- ;//j向后移动
        }

        A[j+1] = temp; //插入temp处的值
    }

}

int main(void)
{
    int A[M];
    int i;
    int n , m;

    printf("请输入数组的值:");
    for(i = 0;i < M;i++)
        scanf("%d",&A[i]);

    printf("\n你输入的值为:");
    for(i = 0;i < M;i++)
        printf("[%d]",A[i]);

    printf("\n");

    insert_sort(A,M);
    for(i = 0;i < M;i++)
        printf("[%d]",A[i]);

    printf("\n");

    printf("请输入你要查找的值:\n");
    scanf("%d",&n);

    m = bin_search(A , M , n);

    if(-1 !=  m){
        printf("排序后,你查找的值在数组的第%d 的位置\n",m);
    }
    else 
        printf("查找失败\n");

    return 0;
}



分析:
输入的值为:10,5,9,8,7

 1. 排序
     首先 i = 1;temp = A[i] = 5; 
             j = i -1 = 0;
             判断j>= 0 && temp < A[0] = 10 ?,判断成立
             A[1] = A[0] = 10;//值交换
             j = -1; 
             判断 j> = 0 判断不成立
             A[1] = 5;
    如此一来:输入的值变为了5,10,9,8,7
    第二轮:i = 2; temp = A[2] = 9;
                  j = i - 1 = 1;
                  判断 j>=0 && temp <A[1] = 10 ?判断成立
                  A[2] = A[1] = 10;//交换值
                  j = 0;
                  判断 j>= 0&& temp < A[0] ?判断不成立
                  A[1] = temp = 9;
        这么一搞:输入值就又变成了:5,9,10,8,7
以此类推,即可将输入数组有序排列为 5,7,8,910

2. 折半查找
    假设要找的值为7 , 即key = 7
    low = 0;
    high = 4;
    mid = 2;
    A[2] = 8 > key ;
    high = mid - 1 = 1;
    mid = 0;
    A[0] = 5 < 7;
    low = mid + 1 = 1;
    mid = 1;
    A[mid] = key; 
    找到7的位置



© 著作权归作者所有

胡若晨
粉丝 3
博文 14
码字总数 7894
作品 0
包头
私信 提问
各种基本算法实现小结(六)—— 查找算法

各种基本算法实现小结(六)—— 查找算法 (均已测试通过) =================================================================== 1、简单查找 在一组无序数列中,查找特定某个数值,并返...

长平狐
2013/01/06
126
0
小朋友学数据结构(6):折半查找法

折半查找法又称为二分查找法。 (一)基本思想 假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子...

海天一树X
2018/05/09
0
0
Java实现的二分查找算法

二分查找又称折半查找,它是一种效率较高的查找方法。 折半查找的算法思想是将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要找...

孟飞阳
2016/06/14
558
0
Java实现的二分查幸运飞艇平台出租找算法[递归]

二分查找又幸运飞艇平台出租 haozbbs.comQ1446595067 称折半查找,它是一种效率较高的查找方法。 折半查找的算法思想是将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先...

oskksk
2018/07/10
0
0
查找——折半查找

一、折半查找 折半查找(Binary Search)又称为二分查找。注意 折半查找方法要求查找表的数据是线性结构保存,并且还要求查找表中的数据是按关键字由小到大有序排列。 折半查找的具体过程 假设有...

翼动动空
2016/06/28
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

YUM仓库配置及命令详解

导读 通过源代码编译的方式安装程序在灵活性、可定制性方面具有无可比拟的优势,但也正因为这种特性给管理员带来了额外的维护开销,当应用在大规模的服务器群集时存在一定的局限性。那么就需...

问题终结者
42分钟前
11
0
docker初学者

docker简介 在真正使用这项技术之前很难深刻的理解它的概念。 从简单的方面来说,docker就是一个轻量级的虚拟机。接下去的学习首先不妨抱着这个想法来看,让后慢慢寻找差别,最终我们会回来试...

街角的小丑
今天
15
0
了解下Hz单位的意思

今天看到计组的突然看到Hz这个单位,突然不知道它是啥意思,就百度了解啦下。 赫,是频率的基本单位,为纪念验证电磁波存在的德国物理学家海因里希·鲁道夫·赫兹(Heinrich Rudolf Hertz)而...

南桥北木
今天
11
0
Mysql的sql_mode模式

sql_mode 是一个很容易被忽视的配置,宽松模式下可能会被输入一些非准确数据,所以生产环境下会要求为严格模式,为了保持生产环境和开发环境,测试环境一致性,我们开发环境和测试环境也要配...

贾峰uk
今天
15
0
Qt程序打包发布方法(使用官方提供的windeployqt工具)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/toTheUnknown/article/details/81748179 如果使用到了Qt ...

shzwork
今天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部