第十四天、二分查找

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

相关文章

来自专栏数据结构与算法

codevs 1213 解的个数

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

3334
来自专栏小灰灰

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

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

7996
来自专栏包子铺里聊IT

那些年我们一起遍历过的树

这篇博文想和大家讨论一下tree的traversal有哪些方法。当然我们都很熟悉DFS(InOrder, PreOrder, PostOrder)和BFS,这...

2617
来自专栏海天一树

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

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

3078
来自专栏chenssy

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

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

1004
来自专栏racaljk

Julia体验 语言基础

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

1582
来自专栏SeanCheney的专栏

《Pandas Cookbook》第01章 Pandas基础

公司网址,http://www.dunderdata.com(dunder是蒸馏朗姆酒的残留液体,取这个名字是类比数据分析过程) GitHub地址:https...

1232
来自专栏菩提树下的杨过

java:POI导出excel

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

2405
来自专栏jeremy的技术点滴

py3_cookbook_notes_01

3138
来自专栏desperate633

HashMap实现原理分析(Java源码剖析)内部实现存储结构-字段功能实现-方法Map中各实现类的总结小结

HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(Java Developmet Kit)版本的更新,JDK1.8对Ha...

692

扫码关注云+社区