C/C++语言100题练习计划 88——猜数游戏（二分查找实现）

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

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

一、问题呈现

1.问题描述

Problem Description

给定n个元素，这些元素是升序的（假定为升序），从中观察特定元素x，即猜一猜x在元素序列中哪个位置？

2.输入输出

Input

第一行：一个整数n，表示数列中元素的个数。
第二行：n个数列元素。
第三行：输入要查找的元素

Output
第一行：输出排序后的数组
第二行：要查找的元素的所在位数（位数默认从1开始）

3.测试样例

Sample Input

11
60 17 39 15 8 34 30 45 5 52 25
17

Sample Output

5 8 15 17 25 30 34 39 45 52 60
4

二、源码实现

#include
#include
#include
#include
using namespace std;
const int Maxn=1e4+5;
int x,n,i;
int s[Maxn];

//二分查找
int BinarySearch(int n,int s[],int x)
{
	int low=0,high=n-1;
	while(low<=high)
	{
		int middle=(low+high)/2;
		if(x==s[middle])
			return middle;
		else if(x<s[middle])
		{
			high=middle-1;
		}
		else 
			low=middle+1;
	}
	return -1;
}
//主函数
int main()
{
	cout<<"请输入数列中的元素个数n为：";
	cin>>n;
	
	cout<<"请依次输入数列中的元素：";
	for(i=0;i<n;i++)
	{
		cin>>s[i];
	}
	//sort快排函数，默认为升序排序
	sort(s,s+n);
	cout<<"排序后的数组为：";
	for(i=0;i<n;i++){
		cout<<s[i]<<" ";
	}
	cout<<endl;
	
	cout<<"请输入要查找的元素：";
	cin>>x;
	//调用二分查找函数进行对该元素的查找
	i=BinarySearch(n,s,x);
	//如果二分查找函数返回值为-1，即i==-1时，说明没有查找到该元素
	if(i==-1)
	{
		cout<<"该数列中没有要查找的元素"<<endl;
	}
	//反之，则查找到，输出所在位置
	else
		cout<<"要查找元素在第"<<i+1<<"位"<<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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

★关于本题思路及二分搜索：

1、本题思路简述

题意：给定n个元素，这些元素是升序的（假定为升序），从中观察特定元素x。
从问题描述来看，如果是n个数，那么最坏的情况要猜n次才能成果，其实我们没有必要一个一个地猜，因为这些数是有序的，它是一个二分搜索问题。我们可以使用折半查找的策略，每次和中间的元素比较，如果比中间元素小，则在前半部分查找（假定为升序），如果比中间元素大，则去后半部分查找。

2、二分查找

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

(上图来源网络，侵删)

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

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

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

三、测试结果

请输入数列中的元素个数n为：11
请依次输入数列中的元素：60 17 39 15 8 34 30 45 5 52 25
排序后的数组为：5 8 15 17 25 30 34 39 45 52 60
请输入要查找的元素：17
要查找元素在第4位

--------------------------------
Process exited after 15.85 seconds with return value 0
请按任意键继续. . .
1
2
3
4
5
6
7
8
9

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