高质量题解|查找x

题目大意

通过二分查找找出 $x$ 的下标，否则输出 $-1$

考纲知识点

输入输出、分支结构、循环结构、算术运算符、一维数组、二分查找、基础数据类型、变量的定义以及使用

数据范围

$0$ $<$ $n$ $≤$ $100$

解题思路

定义 $left$ 和 $right$ ，用来确定区间范围，变量 $mid$ 是中间值的下标

1. $x$ 等于 $a_{mid}$，输出 $mid$ 下标
2. $x$ 小于 $a_{mid}$ 下标的值，$right$ 重新确定范围，因为 $mid$ 已经不等于了，所以从 $mid-1$ 开始
3. $x$ 大于等于 $a_{mid}$ 下标的值，$left$ 重新确定范围，同理

如果以上情况都不符合到最后就代表着找不到 $x$，输出 $-1$

参考程序

#include <bits/stdc++.h>
using namespace std;
int a[1010];
int main(){
	int n,x;
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
	}
	cin >> x;
	//1确定查找范围
	int left = 1,right = n;
	while(left <= right){
		//计算中简值
		int mid = (left + right) / 2;
		if(x == a[mid]){
			cout << mid;
			return 0;
		}else if(x < a[mid]){
			right = mid - 1;
		}else{
			left = mid + 1;
		}
	} 
	cout << -1;
	return 0;
} 

时间复杂度

$O(\log n)$(对数时间复杂度)

空间复杂度

$O(n)$(线性空间复杂度)