输入格式:
第一行输入一个整数n,表示有序表的元素个数,接下来一行n个数字,依次为表内元素值。 然后输入一个要查找的值。

输出格式:
输出这个值在表内的位置,如果没有找到,输出”NOT FOUND”。

输入样例:
5
1 3 5 7 9
7
输出样例:
4
输入样例:
5
1 3 5 7 9
10
输出样例:
NOT FOUND

  1. #include <iostream>
  2. using namespace std;
  3. #define MAXSIZE 50
  4. typedef int KeyType;
  5. typedef struct
  6. { KeyType key;
  7. } ElemType;
  8. typedef struct
  9. { ElemType *R;
  10. int length;
  11. } SSTable;
  12. void Create(SSTable &T)
  13. { int i;
  14. T.R=new ElemType[MAXSIZE+1];
  15. cin>>T.length;
  16. for(i=1;i<=T.length;i++)
  17. cin>>T.R[i].key;
  18. }
  19. //
  20. //方法1,
  21. int Search_Bin(SSTable T, KeyType k)
  22. {
  23. int max=T.length;
  24. int min=0;
  25. bool flag=false;
  26. int count=(max-min)/2+1;//指的是mid
  27. while(count)
  28. {
  29. if(T.R[count+min].key==k)
  30. { flag=true;
  31. break;
  32. }
  33. else if(T.R[count+min].key<k)
  34. {
  35. min=count;
  36. //
  37. //cout<<min+count<<endl;
  38. count/=2;
  39. }
  40. else{
  41. max=count;
  42. //
  43. count=(max-min)/2;
  44. //
  45. }
  46. }
  47. if(flag)
  48. {
  49. return count;
  50. }
  51. else{
  52. return 0;
  53. }
  54. }
  55. //方法2
  56. int Search_Bin(SSTable T, KeyType k)
  57. {
  58. int left=1;
  59. int right=T.length;
  60. int mid=1;
  61. bool flag=false;
  62. while(left<right)
  63. {
  64. mid=(left+right)/2;
  65. if(T.R[mid].key==k)
  66. {
  67. flag=true;
  68. break;
  69. }
  70. if(T.R[mid].key>k)
  71. {
  72. right=mid-1;
  73. }
  74. else{
  75. left=mid+1;
  76. }
  77. }
  78. if(flag)
  79. {
  80. return mid;
  81. }
  82. else{
  83. return 0;
  84. }
  85. }
  86. //
  87. int main ()
  88. { SSTable T; KeyType k;
  89. Create(T);
  90. cin>>k;
  91. int pos= Search_Bin(T,k);
  92. if(pos==0) cout<<"NOT FOUND"<<endl;
  93. else cout<<pos<<endl;
  94. return 0;
  95. }
  96. //两种方法都能ac,都是二分的思想,推荐用第二种,好想和理解,第一种是自己纯想的,第二种是受一篇文章的启发写的
  97. 给一个严格递增数列,函数int Search_Bin(SSTable T, KeyType k)用来二分地查找k在数列中的位置。

函数接口定义:

  1. int Search_Bin(SSTable T, KeyType k)

其中T是有序表,k是查找的值。

裁判测试程序样例:

  1. #include <iostream>
  2. using namespace std;
  3. #define MAXSIZE 50
  4. typedef int KeyType;
  5. typedef struct
  6. { KeyType key;
  7. } ElemType;
  8. typedef struct
  9. { ElemType *R;
  10. int length;
  11. } SSTable;
  12. void Create(SSTable &T)
  13. { int i;
  14. T.R=new ElemType[MAXSIZE+1];
  15. cin>>T.length;
  16. for(i=1;i<=T.length;i++)
  17. cin>>T.R[i].key;
  18. }
  19. int Search_Bin(SSTable T, KeyType k);
  20. int main ()
  21. { SSTable T; KeyType k;
  22. Create(T);
  23. cin>>k;
  24. int pos=Search_Bin(T,k);
  25. if(pos==0) cout<<"NOT FOUND"<<endl;
  26. else cout<<pos<<endl;
  27. return 0;
  28. }
  29. /* 请在这里填写答案 */
点赞(0)
 

0 分

0 人评分

 

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论