专栏首页个人学习总结折半查找 解题报告

折半查找 解题报告

折半查找 解题报告

折半查找是查找方法中的一种,常用的查找方法还有遍历查找。 折半查找运用了二分的思想,也可称为二分查找。其思想是在有序数组a( 必须是有序的,从小到大或从大到小都可以)查找指定元素k,则将数组的中间元素啊a[mid]与k进行比较,如果a[mid]与k相等则已查找到;如果a[mid]与k不等,则需根据a[mid]与k的大小关系,在相应的数组前半段或是后半段中进行查找,不断缩小查找范围(第i次的查找范围是第i-1次的一半),此时需要 递归调用二分查找函数。 二分查找函数可表示为:

int binaryfind(int a[],int k,int low,int high);

其中,a[]代表待查找的数组,k代表查找元素,low和high限定了在数组a中的查找范围,从low-1位置开始查找到high-1位置(因为数组下标从零开始),并且mid=(low+high)。 注意 由于数组a中可能会存在相等的元素,若要求输出k在数组a中第一次出现的位置,可以在第一次查找到与元素k相等的元素位置后,仍然调用二分查找函数,直到查找的范围是1,则此时便找到了元素k在数组a中第一次出现的位置。 例题

题目描述 有n个数(n<=1000000),这n个数已按从大到小顺序存放在一个数组中,然后有T次查询,每次输入一个数,要求用折半查找法找出该数在数组中第一次出现的位置。如果不在数组中输出0。

输入 第一行数组元素的个数n 第二行n个数组元素的值 第三行输入查询次数T (T<=100000) 往下有T行,每行输入一个需要查询的数字 输出 查找的值在数组中的位置

样例输入 10 10 9 8 7 6 5 4 3 2 1 2 9 5 样例输出 2 6

这道题目是典型的折半查找题目,输出查找元素在数组中第一次出现的位置,编写折半查找函数,再进行递归调用即可。 细节注意 1、由于要求n<1000000,直接定义数组无法申请如此大的数组空间,因而要用到malloc函数。(当题目中要求的数组空间比较大时,一定要第一时间想到这样申请空间) 2、在折半查找函数中,如何突显出查找的范围变为1了呢?其实当查找的范围为1时,满足的条件是low=high,此时如果a[mid]==k,代表查找到了k在数组中第一次出现的位置,否则数组中不存在k。(一定要注意这个条件,条件写的不正确的话有的数会查找不到) 代码实现(可能会有瑕疵、冗余,通过了OJ测试)

#include<stdio.h>
#include<stdlib.h>
int binaryfind(int a[],int num,int low,int high) //二分查找函数的定义
{
	int mid;
	mid=(low+high)/2;
	while(low<high)
	{
		if(a[mid]==num) //即便查找到但不一定是第一次出现的位置,继续调用二分查找函数
 		{
			return binaryfind(a,num,low,mid);
		}
		else if(a[mid]>num)
		{
			return binaryfind(a,num,mid+1,high);
		}
		else if(a[mid]<num)
		{
			return binaryfind(a,num,low,mid-1);
		}
	}
	if(low==high && a[mid]==num)   //这个条件是重点,表明查找范围是1,并且a[mid]==num
	{
		return low+1;
	}
	return 0;   //查找不到返回0
}
int main()
{
	int i,m,n;
	int *a=(int *)malloc(1000001*sizeof(int));
	scanf("%d",&m);
	for(i=0;i<m;i++)
	{
		scanf("%d",&a[i]);
	}
	scanf("%d",&n);
	int num;
	for(i=0;i<n;i++)
	{
		scanf("%d",&num);
		printf("%d\n",binaryfind(a,num,0,m-1));
	}
	return 0;
}

(必须熟练了解算法原理,能够熟练写出代码,并注重其中的细节,并不是为了追求提交正确就可以,而是有所思、有所获)

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 折半查找

        public static void main(String[] args) {         int[] nums = {1, 2, 3, 4, ...

    用户2192970
  • 折半查找法

    这个程序用while循环也行,好像while循环看上去更规范,下面写上while循环的示例(来自百度百科):

    栋先生
  • 6.2.2 折半查找

    折半查找,又称二分查找,它适用于有序的顺序表。基本思路是:首先将给定值key与表中中间位置元素的关键字比较,若相等,则查找成功,返回该元素的存储位置;若不等,则...

    week
  • 二分查找---折半查找

    大忽悠爱学习
  • 【查找】折半查找/二分查找

    爱笑的架构师
  • 查找算法:二分查找法(折半查找)

    二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

    仙士可
  • 查找算法之折半查找+分块查找

    跋扈洋
  • 折半查找部分有序

    部分有序 本周qq群有人咨询 Search in Rotated Sorted Array 来源: https://leetcode.com/proble...

    程序员小王
  • 查找算法之顺序查找,折半查找,二叉查找树

      查找表是由同一类型的数据元素构成的集合。例如电话号码簿和字典都可以看作是一张查找表。   在查找表中只做查找操作,而不改动表中数据元素,称此类查找表为静态...

    嵌入式与Linux那些事
  • java中二分查找(折半查找)的写法

    用户1696846
  • 数据结构 折半查找法

    时间复杂度: log 2 n + 1 平均查找长度: log 2 n + 1 – 1

    Meng小羽
  • 关于快速查找法(折半/二分查找法)解释(一次记住)binarysearch

    low区的数据就放弃了,怎么放弃low区?直接把最low的位置指到mid的位置就行了,但还不够,还要多移一位才行(low=mid+1)。

    全栈程序员站长
  • 算法与数据结构(九) 查找表的顺序查找、折半查找、插值查找以及Fibonacci查找(Swift版)

    今天这篇博客就聊聊几种常见的查找算法,当然本篇博客只是涉及了部分查找算法,接下来的几篇博客中都将会介绍关于查找的相关内容。本篇博客主要介绍查找表的顺序查找、折半...

    lizelu
  • 小朋友学数据结构(6):折半查找法

    假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键...

    海天一树
  • iOS开发之使用CocoaPods更新第三方出现“target overrides the `OTHER_LDFLAGS`……”问题解决方案

      今天在自己的项目中用CocoaPods引入第三方SDWebImage的时候,出现了问题。当更新完毕后,在终端没太注意这个问题的提示,就直接使用SDWebIm...

    lizelu
  • 2018.10.25解题报告

    T1:直接贪心即可。最优策略显然是用第一个序列的大的 和 第二个序列的小的放在一起

    attack
  • 2017.11.7解题报告

    预计分数:100+0+40=140 实际分数:100+0+0=100 震惊!出题人的一张机票可以用无限次 T1https://www.luogu.org/pro...

    attack
  • 10.25解题报告

    预计分数:40+50+4=94 实际分数:30+15+0=45 T1 https://www.luogu.org/problem/show?pid=T14791...

    attack
  • 2017.10.23解题报告

    预计分数:100+60+0=160 实际分数:100+80+0=180 T1 题目描述 现在有一个字符串,每个字母出现的次数均为偶数。接下来我们把第一次出现的字...

    attack

扫码关注云+社区

领取腾讯云代金券