-
2021-02-22 22:07:11
设n个不同的整数排好序后存于T[0:n-1]中. 若存在若干(>=0)个下标i,0<= i <=n-1, 使得T[i]=i. 设计一个有效算法找到这些个下标.
数据输入: 第1行有一个正整数n, n<=1000000, 表示有n个整数(保证在int内). 接下来一行是这n个整数.
结果输出:T[i]=i的下标;若没有则输出No .注意输出最后有个空格.
测试输入 期待的输出 时间限制 内存限制 额外进程 测试用例 1 以文本方式显示 - 2↵
- 0 1↵
以文本方式显示 - 0 1 ↵
1秒 64M 0 #include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int N=1e6+5; int n,a[N],b[N],s=0,flag=1; void bs(int l,int r) { int mid=(l+r)/2; if(l<=r) { if(a[mid]==mid) { b[s]=mid; s++; bs(l,mid-1); bs(mid+1,r); } else if(a[mid]<mid) { if(flag) bs(mid+1,r); else bs(l,mid-1); } else if(a[mid]>mid) { if(flag) bs(l,mid-1); else bs(mid+1,r); } } } int main(){ cin>>n; for(int i=0;i<n;i++) scanf("%d",&a[i]); if(a[0]>a[n-1]) flag=0; bs(0,n-1); if(s>0) { sort(b,b+s); for(int i=0;i<s;i++) printf("%d ",b[i]); printf("\n"); } else printf("No \n"); }
更多相关内容 -
数据结构习题二分找下标程序
2021-04-04 11:22:14数据结构习题二分找下标程序 -
【C语言】二分查找求数组下标
2022-04-23 19:42:28有n个数存放在一个数组a[]中,输入一个数k,要求用折半查找求出k是数组中第几个元素的值,求该元素的下标;若k不属于数组中任何一个元素,则输出“None”。 方法一:不利用函数利用数组循环等求下标 #include<...目录
题目:
有n个数存放在一个数组a[]中,输入一个数k,要求用折半查找求出k是数组中第几个元素的值,求该元素的下标;若k不属于数组中任何一个元素,则输出“None”。
方法一:不利用函数利用数组循环等求下标
#include<stdio.h> int main() { int a[100], k, i, mid, n, flag = 0; scanf("%d", &n);//输入数组的长度 int left = 0;//首元素下标 int right= n - 1;//末元素下标 for (i = 0; i < n; i++) scanf("%d", &a[i]);//输入所有的数字 scanf("%d", &k);//输入要查找的数字 while (left <= right)//保证left <= right(下标) { mid = left + (right - left) / 2;//二分查找,求中间位置--注意溢出 //mid = (left + right)/2;//未考虑溢出情况 if (a[mid] == k)//先考虑相等的情况可以少比较两次 { printf("%d\n", mid);//a[mid]=k,查找成功 flag = 1;//查找成功flag=1 break; } else { if (a[mid] < k) left = mid + 1; else right = mid - 1; } } if (flag == 0)//查找失败,flag仍为0(原来的数) printf("None\n"); return 0; }
先输入数组的长度(元素的个数)n,利用for循环语句随机输入n个数,再输入一个数k,若k在该数组中,在while循环语句中利用二分查找(折半查找)和if语句求元素k的下标,如果k不在该数组中,输出None,(利用flag判断k是否在该数组中)。
运行结果如下:
方法二:利用函数法求下标
#include<stdio.h> int binary_search(int a[], int k, int n) { int left = 0; int right = n - 1; int flag = 0; while (left <= right) { int mid = left + (right - left) / 2;//防溢出 //int mid = (left + right) / 2; if (a[mid] > k) { right = mid - 1; } else if (a[mid] < k) { left = mid + 1; } else { printf("%d\n", mid); flag = 1;//找到元素则flag=1 break;//然后结束该循环 } } if (flag == 0)//若输入的数k不在该数组中 printf("None\n");//则输出None } int main() { int a[100]; int k, s, i, n; scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &a[i]); scanf("%d", &k);//找到就返回找到位置的下标 //数组arr传参传递的只是数组首元素的地址 int ret = binary_search(a, k, n); return 0; }
调用函数binary_search求该下标,其他方法和方法一类似
其运行结果如下:
本来是利用调用函数方法求该下标的,后来在朋友的提醒下利用数组之前的知识求出随机值的下标,没学过函数的朋友们可以借鉴一下啦!有错误欢迎指出嘿嘿。
-
Python查找数组中数值和下标相等的元素示例【二分查找】
2020-12-26 05:27:49采用二分查找:如果数组中的数字小于下标,由于下标是-1的递减数列,但是数组中的元素差值大于等于-1,因此左边的不可能等于下标。如果数组中的数字大于下标,同理,之后的数字肯定都大于下标,往左边查找。 算法... -
PHP教程:二维数组二分查找需找数组中某一元素下标.doc
2020-03-08 00:34:30php教程二维数组二分查找需找数组中某一元素下标 成功不是将来才有的而是从决定去做的那一刻起持续累积而成以下的在PHP中二维数组二分查找需找数组中某一元素下标希望对大家有所帮助更多信息请关注 如果你的数组有... -
C语言--折半查找法/二分查找法 找下标
2022-01-23 23:01:06 -
二分查找(查找下标以及初始结束位置)
2020-07-09 10:21:42注意:此处所指的二分之一指的是数组下标,而比较的却是数组中的值。 eg: 给定一个数组和目标值,运用二分查找,若找到,则输出它所在 的位置;未找到,就输出-1; #include<stdio.h> int a[10]= {0,1,2,3,4,...1.寻找单个元素的准确下标
思路:主要是将区间段中二分之一的值与目标值进行比较,然后慢慢缩小区间,直至寻到目标值。
注意:此处所指的二分之一指的是数组下标,而比较的却是数组中的值。
eg: 给定一个数组和目标值,运用二分查找,若找到,则输出它所在 的位置;未找到,就输出-1;#include<stdio.h> int a[10]= {0,1,2,3,4,5,6,7,8,9}; int main() { int t,l=0,r=9,mid=0,ans=0; //r,l 分别代表数组的左右两端 scanf("%d",&t); //给定一个目标值 while(l<=r) //进行循环,结束条件是当区间缩减到只有那个数时 { mid=(l+r)/2; //下标的中间值 if(a[mid]>t) //将中间值与目标值作比较 r=mid-1; //如果小于,就说明目标值在中间值的左边,因此将右界限改变 else if(a[mid]<t) //同理,大于目标值,就将左边界改变 l=mid+1; else { ans=mid; //直至寻找到目标值,终止循环 break; } } printf("%d",ans); }
2.寻找一个元素在数组中的初始位置和结束位置
#include<stdio.h> int a[10]= {1,1,1,2,3,3,4,5,6,6}; //数组元素 int main() { int n; scanf("%d",&n); //输入一个可查询的数 int r,l,s=0,e=9,mid=0; while(s<=e) { //寻找元素左边界 mid=(s+e)/2; //依然是中间值比较 if(a[mid]>=n) //即使寻找到n时,也继续比较,不停止 e=mid-1; else s=mid+1; //终止条件,当寻找到左边界时,才会出循环 } l=s,s=0,e=9; //赋值,左边界;同时归零,回到初始状态 while(s<=e) { //寻找右边界,理解同上 mid=(s+e)/2; if(a[mid]<=n) s=mid+1; else e=mid-1; } r=e; printf("%d %d\n",l,r);//输出即可 }
_ 同是用二分查找的方法进行,这个里面用了两次,分别寻找左右边界。
与案例一不同的是,案例一中寻找到所需要的值即可跳出循环;但是,案例二中不同的是,即使寻找到了,也不停止,直至寻找到边界为止,(可见代码中的>=和<=)。
此时,循环会执行到左边界左边的值和右边界右边的值,就会跳出循环,输出就找到啦 _ -
二分查找返回key在数组中的位置(下标),有注释
2011-09-26 15:59:08二分检索 二分查找 key C++ 返回key在数组中的位置(下标),有注释 -
HBU训练营——二分查找 (15分)(利用二分查找找出所给出的数在数组中的下标)
2020-07-19 19:19:27利用二分查找找出所给出的数在数组中的下标 输入格式: 第一行输入n和m表示数组有n个数据,m表示要对m个数进行查找 输出格式: 所有输出在一行完成,行末没有多余空格和多余回车。 输入样例: 5 5 1 2 3 4 5 1 2 3 4 5... -
C语言程序设计实现二分查找算法
2019-04-13 15:09:49《二分查找算法》 1)将二分查找元素算法分为三个部分输入元素、查找元素、进行判断! 2)如果查找的元素在原始的元素中找不到话可以进行判定是否进行重新输入,查找,可以选择拒绝1 3)输入原始元素使用升序输入,... -
二分查找方便查找数,得到下标
2011-06-20 20:34:14功能:二分查找 可以找到该数的下标 速度快 运行简单 -
Python通过二分查找,查询有序列表中元素的下标
2020-04-16 20:34:08Python通过二分查找,查询有序列表中元素的下标 为什么使用二分查找? 因为二分查找可以快速的查找一个有序列表中的元素 注意:查找的对象必须是一个有序的列表!!!! 代码示例 通过while循环的方式可以... -
c语言:用二分查找算法,查找有序数组的下标
2021-11-07 21:19:10#include int main() { int arr[] = { 1,2,3,4,5,6,7,8,9 }; int k = 7; int sz = sizeof(arr) / sizeof... } else { printf("下标是:%d\n", mid); break; } } if (left > right) { printf("找不到\n"); } return 0; } -
二分查找找下标或者值
2015-10-20 22:04:48} //二分查找找出下标 public static int middleSort(int value,int[] a){ // boolean boo=false; int mid=a.length/2; int min=0; int i=1; int max=a.length-1; while(ia[mid]){ min=mid; mid=(min+max)/2; ... -
采用二分查找法和顺序查找法查找元素的下标
2010-06-03 15:53:57编写程序对数据序列采用二分查找法和顺序查找法查找元素的下标,要求使用类模板实现(其中二分法查找算法要求用递归实现,给定数据序列有序)。 -
二分查找 输出元素下标
2018-03-09 13:13:03#define n 6/* 折半查找法找出该数是数组中第几个元素的值,如果不在数组中,则输出”无此数”*/int main(int argc, char *argv[]) { int a[n]={1,3,5,7,9,10};// 012345 5/2=2 4<5 and mid-1 //////... -
LeetCode 1095. 山脉数组中查找目标值(二分查找)
2020-12-21 02:58:13给你一个 山脉数组 mountainArr,请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。 如果不存在这样的下标 index,就请返回 -1。 何为山脉数组?如果数组 A 是一个山脉数组的话,那它... -
在数组中进行二分查找找出某数在数组中的下标
2014-05-22 19:17:28//java import java.util.Scanner; /** * @author 刘育新 ... * 二分查找 */ public class Binary_search { public static int device(int[] a,int c) { int begin=0; int end=a.lengt -
二分查找在有序数组寻找第一个大于等于目标元素的下标
2020-03-16 10:33:59while(low<high) { mid=(low+high)/2; if(dtat[mid]>=traget) high=mid; else low=mid+1; } //这里不能用 ...如果这样写的话,当low和 high相邻,且low恰好存储的就是小于等于traget的值的时... -
【数据结构】Java语言二分查找数组中的下标
2019-02-25 22:47:12* Goal:用二分查找算法找出一个数在数组中的下标 * Author:Tang.Mitnick * Site:FaFu * */ //设计思想:对一个数组中的数组进行折半查找,确定给出的数对应的在数组中的下标。 public class BinarySearch { ... -
找出升序排序数组第一个小于目标值的所有下标,第一个大于目标值的所有下标——四次二分搜索
2020-09-25 12:12:34题目:找出升序排序数组第一个小于目标值的所有下标,第一个大于目标值的所有下标——四次二分搜索 思路: 1. 第一次二分:找目标值的最左下标 2. 第二次二分:找小于目标值的第一个数的值的最左边界 3. 第三次... -
数组中数值和下标相等的元素(二分查找)
2018-12-11 09:55:20采用二分查找:如果数组中的数字小于下标,由于下标是-1的递减数列,但是数组中的元素差值大于等于-1,因此左边的不可能等于下标。如果数组中的数字大于下标,同理,之后的数字肯定都大于下标,往左边查找。 class ... -
python笔试例题(快速排序、二分查找、最长无重复子串、最长回文串长度、输出数组中两数相加=target的下标...
2021-12-03 10:55:06python笔试例题(快速排序、二分查找、最长无重复子串、最长回文串长度、输出数组中两数相加=target的下标、用两 -
编程题:使用二分查找法,查找第一个大于或等于某个数的下标
2018-10-08 13:50:24题目要求:使用二分查找法,查找出第一个大于或等于某个数的下标 例如:int[]a = {1,2,2,2,4,8,10},查找2,返回第一个2的下标1,查找3返回4的下标4,查找4返回4的下标4,如果没有则返回-1. #include <... -
二分查找法
2020-12-28 22:53:17二分查找法(Binary Search)算法,也叫折半查找算法。二分查找针对的是一个有序的数据集合,查找思想有点类似于分治思想。每次都通过跟区间的中间元素对比,将带查找的区间缩小为之前的一半,直到找到要查找的元素... -
陈越、何钦铭-数据结构作业1:二分查找算法
2018-03-15 21:37:35L是用户传入的一个线性表,其中ElementType元素可以通过>、==、<进行比较...函数BinarySearch要查找X在Data中的位置,即数组下标(注意:元素从下标1开始存储)。找到则返回下标,否则返回一个特殊的失败标记NotFound。 -
二分查找(在整型有序数组中查找想要的数字,找到了返回下标,找不到返回 - 1)
2018-04-01 14:12:15在整型有序数组中查找想要的数字,找到了返回下标,找不到返回 - 1#include<stdio.h> #include<Windows.h> int binary_search(int arr[], int key, int sz) { int left = 0; int ... -
java查找算法:二分查找(两种方式)
2022-02-12 11:19:45二分查找算法思想 二分查找针对的是一个有序的数据集合也就是数组(这也成为了二分查找的一个重要局限性),查找思想有点类似分治思想。 每次都通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到... -
二分查找步骤总结
2019-02-10 13:26:586种二分查找及其变式总结及牢记方法 假设数组为:int arr[] = { 1,2,3,3,4,5,5,8,10,12 };(数组从小到大排序) 先从最开始的两个二分查找入手,通过细节变形而总结出6中二分查找: - 查找第一个等于key的元素...
收藏数
216,047
精华内容
86,418