第十四天、二分查找

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

相关文章

来自专栏数据结构与算法

3089:爬楼梯

3089:爬楼梯 总时间限制: 1000ms 内存限制: 65536kB描述 树老师爬楼梯,他可以每次走1级或者2级,输入楼梯的级数,求不同的走法数 例如:...

3335
来自专栏Hongten

一看就懂的冒泡排序方法_java版

=================================================

762
来自专栏小鹏的专栏

tf API 研读4:Inputs and Readers

tensorflow中数据的读入相关类或函数: 占位符(Placeholders) tf提供一种占位符操作,在执行时需要为其提供数据data。 操作 描...

35610
来自专栏青青天空树

小白初理解树状数组

  ACM的在线测试里经常涉及到大量数据的的修改,求和等操作,这里介绍一种方法——树状数组。

592
来自专栏恰同学骚年

数据结构基础温故-2.栈

现实生活中的事情往往都能总结归纳成一定的数据结构,例如餐馆中餐盘的堆叠和使用,羽毛球筒里装的羽毛球等都是典型的栈结构。而在.NET中,值类型在线程栈上进行分配,...

503
来自专栏蛋未明的专栏

Node服务器程序面向对象编程

1574
来自专栏大数据架构

Java进阶(一)Annotation(注解)

Annotation是Java5开始引入的特性。它提供了一种安全的类似于注释和Java doc的机制。实事上,Annotation已经被广泛用于各种Java框架...

4127
来自专栏蓝天

类型安全的变参函数any2string(),可用来替代类型不安全的snprintf()

any2string.sh用来生成any2string.h和test_any2string.cpp两个文件: https://github.com/eyjia...

392
来自专栏编程

python及numpy,pandas易混淆的点

初接触python觉得及其友好(类似matlab),尤其是一些令人拍案叫绝不可思议的简单命令就可以完成非常复杂的计算,但是真正接触一下就发现,python比ma...

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

洛谷P1435 回文字串(dp)

首先不难看出,这题跟LCS有关,而且是魔改版的LCS,具体来说,我们要求的是前缀$1 - i$的反串和后缀$i - n$的LCS。

561

扫码关注云+社区