第十四天、二分查找

题目     采用二分查找法查找特定关键字的元素。要求用户输入数组长度,也就是有序表的数据长度,并输入数组元素和查找的关键字。程序输出查找成功与否,以及成功时关键字在数组中的位置。例如,在有序表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 条评论
登录 后参与评论

相关文章

来自专栏程序你好

如何在Java和Swift中避免空引用异常?

您最近在代码中遇到过NullPointerException(空指针异常)吗? 如果没有,那你一定是一个很细心的程序员。在Java应用程序中最常见的异常类型之一...

683
来自专栏Alice

IOS6学习笔记(三)

1.ARC空声明变量   使用ARC的另一个优势是所有未初始化的变量默认都是“空值化”的。这意味着像下面这样的声明使用ARC编译后指向的是空值(nil):  ...

1729
来自专栏xingoo, 一个梦想做发明家的程序员

Elasticsearch——多索引的使用

在Elasticsearch中,一般的查询都支持多索引。 只有文档API或者别名等不支持多索引操作,因此本篇就翻译一下多索引相关的内容。 首先,先插入几...

1877
来自专栏互联网杂技

node中Express的use深入理解

Express的API 现在学node,不来点Express,都不好意思给人打招呼。但是,我刚接触的时候,觉得好多API,感觉乱糟糟的,没办法,大脑容量不够。不...

2854
来自专栏数据处理

pandas之concat and merge

1034
来自专栏Golang语言社区

Go语言核心之美 -JSON

JSON(JavaScript Object Notation)是一种发送和接收结构化信息的标准化表示法。类似的标准化协议还有XML、ASN.1、Protobu...

3446
来自专栏技术小讲堂

iBatis.Net(6):Data Map(深入)

在上一篇中,我写了几个最最基本的DataMap映射,但是如果仅仅是这些功能的话,那iBatis真就有点愧对它的粉丝啦,我个人的理解,iBatis真的可以让开发者...

2879
来自专栏冰霜之地

Objc 对象的今生今世

在面向对象编程中,我们每天都在创建对象,用对象描述着整个世界,然而对象是如何从孕育到销毁的呢?

781
来自专栏技术栈大杂烩

Python: C扩展初体验

使用 Python 毋庸置疑减少了很多规则约束和开发成本,让我们能够更加专注于逻辑而非语法。但是得此失彼,开发效率提高了,却带来了运行性能的问题,所以就常常被其...

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

《Kotlin极简教程》第3章 Kotlin语言基础第3章 Kotlin语言基础《Kotlin极简教程》正式上架:参考资料

学习任何东西,都是一个由表及里的过程。学习一门编程语言也一样。对于一门编程语言来说,“表” 就是基本词汇(关键字、标识符等)、句子(表达式)和语法。

1122

扫码关注云+社区