C语言折半查找法的超详细讲解
作者:一个爱好编程的大学生i 发布时间:2022-10-26 19:33:16
标签:c语言,折半,查找
折半查找法仅适用于对已有顺序的数组、数据进行操作!!!(从小到大)自我总结:折半查找法就是相当于(通过改变low或high的大小)把中间位置指到了key那个数那里,所以mid应该处于循环里面,即mid=(high+low)/2。注意:low,mid,high都要与下标绑定,也就是说它们就是下标。且循环条件是:high>=low.
同时注意:⑴若原来数组是由小到大排列的则:
mid=(high+low)/2;
if(key<a[mid])//说明要找的值在左边
high=mid-1;
else if(key>a[mid])//说明要找的值在mid右边
low=mid+1;//最小值的位置往右进一位
㈡若原来数组是由大到小排列的则:
mid=(high+low)/2;
if(key>a[mid])//注意是由大到小排列 ,所以此时key在a【mid】 左边,故high=mid-1 ;
high=mid-1;
else if(key<a[mid])//注意是由大到小排列,所以此时key在a【mid】右边,故low=mid+1;
low=mid+1;
当然在下面这个代码中,也可以用选择排序法和冒泡法来对任意数组进行排序,然后在应用此函数,保证折半查找法的前提是排好序了。
#include<stdio.h>
void zb(int key,int a[],int n)//key表示要找的数,a表示数组,n表示数组元素个数
{
int i,high,low,mid;
int count1=0,count=0;
low=0;
high=n-1;
while(high>=low)//保证右下标不小于左下标
{
count++;
mid=(high+low)/2;//总的来说变得是中间位置相当于把中间位置移到了key那个数那里,所以mid应该处于循环里面
if(key<a[mid])//说明key在a【mid】的左半边 ,那么最右边的high下标就可以在下标mid基础上往左进一个单位了
high=mid-1;
else if(key>a[mid])//说明key在a【mid】的右半边 ,那么最左边的low下标就可以在下标mid基础上往右进一个单位了
low=mid+1;
if(key==a[mid])
{
printf("元素找到了!!!\n一共查找了%d次\n它处于a[%d]位置上\na[%d]=%d\n",count,mid,mid,key);
count1++;
break;
}
}
if(count1==0)
printf("元素不存在!!!\n");
}
int main ()
{
int key,n,a[100];
int i;
void zb(int key,int a[],int n);//声明定义函数
printf("请输入数组元素个数:\n");
scanf("%d",&n);
printf("请输入(从小到大)所有数组元素:\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("请输入要查找的数:\n");
scanf("%d",&key);
zb(key,a,n);
printf("\n");
return 0;
}
来源:https://blog.csdn.net/m0_56168966/article/details/121390236
0
投稿
猜你喜欢
- 在一些允许用户自定义栏目顺序的app(如:凤凰新闻、网易云音乐等),我们可以方便地拖拽列表项来完成列表的重新排序,进而完成对栏目顺序的重排。
- 本文实例讲述了C#逐行读取文件的方法。分享给大家供大家参考。具体如下:这里使用C#逐行读取文件,对于大文件的读取非常有用。StreamRea
- 前言最近看插件库上少有的取色器大都是圆形的或者奇奇怪的的亚子,所以今天做两个矩形的颜色取色器提示:以下是本篇文章正文内容,下面案例可供参考一
- 一、this可以代表引用类的当前实例,包括继承而来的方法,通常可以省略。public class Person{ &n
- Alt+Enter快捷键是Idea中比较特殊的一个快捷键。它有很多功能,比如:导入包,自动修正代码 解决出现的问题 也可以生成返回值。这里有
- 目录1.文件读写1.1打开文件1.2关闭文件1.3读取文件1.4写入文件1.5读写二进制I/O文件1.6获取文件的大小1.7文本简单加密、解
- 本文实例为大家分享了java实现马踏棋盘的具体代码,供大家参考,具体内容如下马踏棋盘算法介绍8X8棋盘,马走日字,要求每个方格只进入一次,走
- 第三章 字符串,比较器和过滤器JDK引入的一些方法对写出函数式风格的代码很有帮助。JDK库里的一些的类和接口我们已经用得非常熟悉了,比如说S
- 要理解实现原理,必须把线程池的几个参数彻底搞懂,不要死记硬背一、线程池参数1、corePoolSize(必填):核心线程数。2、maximu
- 首先对图片进行UUID 防止图片被覆盖以及爬图UUID的生成规则:日期时间,MAC地址,HashCode,随机数(多种之一)开发上传接口,两
- Java8 HashMap键与Comparable接口最容易使 HashMap 发生哈希冲突的方法是什么呢?我们可以创建一个类,让它的哈希函
- @RequestBody,@RequestParam和@Param区别@Param@Param是mybatis中的注解,用注解来简化xml配
- SpringBoot访问html和js等静态资源配置把静态资源放到resources/static下,这是springboot静态资源默认访
- 目录引言什么是Span关于String的一段性能提升测试代码最终性能对比写在最后引言C# 是一门现代化的编程语言,与Java十分的相似。熟练
- FastDFS简介FastDFS是一款开源的轻量级分布式文件系统,使用C实现,支持Linux、BSD等unix-like操作系统。值得注意的
- 1、背景最近用到了Spring Cloud Alibaba开发微服务,在开发的过程中发现,当我们的服务上线或下线的时候,我们的Spring
- 基本结构我们先来看一段最基本的代码,分析这段代码在RxJava中是如何实现的。Observable.OnSubscribe<Strin
- 1.抽象类与抽象方法:(1)使用关键字abstract修饰的类,称为抽象类.(2)抽象类只是用到一个类所具有的行为,不能单独通过创建对象来使
- Java for循环打印菱形Java代码输出菱形的方法和思路有很多,在此分享一个稍带模块化拆分思想的解决方案,将需要输出的菱形拆分成8个模块
- 开发环境:IntelliJ IDEA 2019.2.2Spring Boot版本:2.1.8一、发布REST服务1、IDEA新建一个名称为r