C/C++语言100题练习计划 80——好多好多符（二分查找实现）

名人说：故立志者，为学之心也；为学者，立志之事也。—— 王阳明
进度：C/C++语言100题练习计划专栏，目前80/100

🥇C/C++语言100题练习专栏计划：目的：巩固练习C/C++语言，增强上机、动手实践能力，交流学习！

一、问题呈现

1.问题描述

Problem Description
曾经有位大贤，将各种仙法编纂进了《道法三千》的书中，并给每种道法一个编号。书名虽然唤作《道法三千》，但是实际上的道法数远远超过三千，这本书现在已经是云之界广泛流行，于是，各大门派都使用这本书中的道法编号来标识道法。

小云是修行世家，然而天赋奇差，难以修习道法。所幸小云拥有大量家族赐予的道符，使用道符可以直接使用道法。

每张道符上有一个道法编号，代表这张道符可以直接使用出来的道法。

小云心中有q个诸如“ b${}_i$道法我能否使用”的问题。由于小云的道符和疑问太多了，所以，它需要神奇的你来帮助他。

2.输入输出

Input

第一行一个整数 n 。表示道符张数。

第二行 n 个以空格隔开的整数，第i个数表示 a${}_i$。含义见题目描述。

第三行一个正整数 q ， 表示小云的疑问数。

第四行 q 个以空格隔开的正整数，第 i 个数表示 b${}_i$。含义见题目描述。

Output

输出仅一行，为一个长度为n的字符串s。当小云可以使用出道法b${}_i$时输出s${}_i$=‘Y’,否则 s${}_i$= ‘N’。

3.测试样例

Sample Input

10
5 5 6 8 8 9 12 23 41 79
15
50 8 9 23 233 5 6 8 79 12 5 8 9 41 22

Sample Output

NYYYNYYYYYYYYYN

★提示：
对于50%的数据：1<=n,q<=5000
对于100%的数据：1<=n,q<=10^6
1<=a${}_i$,b${}_i$<=q<=2^31-1

二、源码实现

#include
#include
#include
using namespace std;
const int maxn=1e6+5;
int a[maxn];
int n,q,b;
string S;
//二分查找
int find(int x)
{
    int l=1,r=n;
  	while(l<=r)
    {
      int mid=(l+r)>>1;
      if(x==a[mid]) return 1;
      else if(x<a[mid]){
	  	r=mid-1;
	  }  
      else l=mid+1;
    }
    return -1;//如果二分查找未找到，返回-1
}

int main()
{
	//输入n的值代表道符张数
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
        scanf("%d",&a[i]);
    //输入q的值代表小云的疑问数
    scanf("%d",&q);
    for(int i = 1;i <= q;i ++){
        scanf("%d",&b);
        //如果二分查找返回的结果不是-1 代表小云可以使出道法bi
        if(find(b) != -1)
            S += 'Y';
        //反之如下
        else
            S += 'N';
    }
    //输出最终的字符串
    cout<<S<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

★关于二分查找：
二分查找又称折半查找、二分搜索、折半搜索等，是在分治算法基础上设计出来的查找算法，对应的时间复杂度为O(logn)。
大家可以现看下这张gif图，能够看出二分查找和遍历查找的效率对比效果(上半部分为二分，下半部分为遍历)：

(上图来源网络，侵删)

1️⃣二分查找
在有序序列中，使用二分查找算法搜索目标元素的核心思想是：不断地缩小搜索区域，降低查找目标元素的难度。
二分思想其实可以理解为是一种将一个大问题分成两个子题，当每次分析完两个子问题后，舍弃其中一个不符合条件的子问题，再将符合条件的子问题一分为二，反复循环搜索判断的操作，直至找到所求的数值或者子问题不能再一分为二时为止的思想。

2️⃣总结
二分查找简单来说的话是在一个已知的有序数据集上进行二分地查找。
例如：在已知有序序列 3 5 7 8 9 12 15，查找元素9

值得注意的是：二分查找算法仅适用于有序序列，它只能用在升序序列或者降序序列中查找目标元素。

三、测试结果

10
5 5 6 8 8 9 12 23 41 79
15
50 8 9 23 233 5 6 8 79 12 5 8 9 41 22
NYYYNYYYYYYYYYN

--------------------------------
Process exited after 0.8455 seconds with return value 0
请按任意键继续. . .

1
2
3
4
5
6
7
8
9
10

Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder）
如果对大家有帮助的话，希望大家能多多点赞+关注！这样我动力会更足哦！ ღ( ´･ᴗ･` )比心