第十四天、二分查找

题目     采用二分查找法查找特定关键字的元素。要求用户输入数组长度,也就是有序表的数据长度,并输入数组元素和查找的关键字。程序输出查找成功与否,以及成功时关键字在数组中的位置。例如,在有序表11、13、18、28、39、56、69、89、98、122中查找关键字为89的元素。 1、程序分析     二分查找就是折半查找,其基本思想是:首先选取表中间位置的记录,将其关键字与给定关键字key进行比较,若相等,则查找成功;若key值比该关键值大,则要找的元素一定在右子表中,则继续对右子表进行折半查找;若key值比该关键值小,则要找的元素一定在左子表中,继续对左子表进行折半查找。如此递推,直到查找成功或查找失败(查找范围为0)。 2、程序实现

/******************************************************
 * Topic    :   采用二分查找法查找特定关键字的元素。
 * File Name:   BinarySearch.c
 * Author   :   Jack Cui
 * Created  :   6 April 2016
 * ****************************************************/

#include <stdio.h>
#include <stdlib.h>
/*归并排序函数声明*/
void BinarySearch(int iKey,int *pArr,int iNum);

void main(void)
{
    int i,iKey,*pArr,iNum;
    printf("请输入数组的长度:\n");
    scanf("%d",&iNum);
    printf("请输入数组元素:\n");
    pArr = (int *)malloc(sizeof(int) *iNum);
    for(i = 0;i < iNum;i++)
        scanf("%d",&pArr[i]);
    printf("请输入你想查找的元素:\n");
    scanf("%d",&iKey);
    BinarySearch(iKey,pArr,iNum);
}

/**********************************
*函数名称:BinarySearch
*参数说明:iKey      要查找的数
*         *pArr     数组
*         iNum      数组大小
*说明:    二分查找
***********************************/
void BinarySearch(int iKey,int *pArr,int iNum)
{
    int iLeft,iRight,iMid,iCount,iFlag;
    iCount = 0;                         //记录查找次数
    iFlag = 0;                          //查找正确标志位
    iLeft = 0;                          //左侧最小值
    iRight = iNum - 1;                  //右侧最大值
    while(iLeft <= iRight)              //范围正确的时候,进行查询。
    {
        iCount++;                       //查找次数+1
        iMid = (iLeft + iRight) / 2;    //二分
        if(iKey < pArr[iMid])
            iRight = iMid - 1;
        else if(iKey > pArr[iMid])
            iLeft = iMid + 1;
        else if(iKey == pArr[iMid])
        {
            printf("查找成功!\n查找%d次!pArr[%d]=%d\n",iCount,iMid,iKey);
            iFlag = 1;
            break;
        }
    }
    if(iFlag == 0)
        printf("查找失败!\n");
}

3、结果显示

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏about云

Scala的map实现key和value排序及各种排序比较等知识讨论

问题导读 1.map能否直接排序? 2.如何转换,才能排序? 3.排序结果可以存储在哪两个集合中? 4._*如何使用? 5.排序函数中,哪个可以进行升序和降序...

41780
来自专栏chenssy

【死磕 Spring】—– IOC 之构造函数实例化 bean

createBeanInstance() 用于实例化 bean,它会根据不同情况选择不同的实例化策略来完成 bean 的初始化,主要包括:

16340
来自专栏Python攻城狮

Python数据科学(七)- 资料清理(Ⅱ)1.资料转换2.处理时间格式资料3.重塑资料4.学习正则表达式5.实例处理

注意:这里的时间转换后的格式可以根据需要设定,eg:dt.strftime('%Y/%m/%d')

12730
来自专栏数据结构与算法

codevs 1213 解的个数

1213 解的个数 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 已知整数x...

34440
来自专栏Golang语言社区

实效go编程--2

Go函数的返回值或结果“形参”可被命名,并作为常规变量使用,就像传入的形参一样。 命名后,一旦该函数开始执行,它们就会被初始化为与其类型相应的零值; 若该函数执...

35470
来自专栏racaljk

Julia体验 语言基础

以前听说过Julia,不过那时候官网还处于时不时宕机状态,最近Julia发布了1.0 released版本到处都是它的资讯,官网良心自带简体中文,趁着热度我也来...

23120
来自专栏小灰灰

java之通过反射生成并初始化对象

java之通过反射生成并初始化对象 在博文 《java之的读取文件大全》 中读取csv文件后,需要自己将csv文件的对象转为自己的DO对象,那么有没有办法我...

1.3K60
来自专栏菩提树下的杨过

java:POI导出excel

POI是一个开源项目,专用于java平台上操作MS OFFICE,企业应用开发中可用它方便导出Excel. 下面是使用示例: 1、maven中先添加依赖项 1 ...

37260
来自专栏海天一树

程序员必须掌握的8大排序算法

分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基数排序)...

34780
来自专栏一个会写诗的程序员的博客

《Kotlin极简教程》第五章 Kotlin面向对象编程(OOP)一个OOP版本的HelloWorld构造函数传参Data Class定义接口&实现之写pojo bean定一个Rectangle对象封

We frequently create a class to do nothing but hold data. In such a class some s...

26340

扫码关注云+社区

领取腾讯云代金券