P8481 Binary search

题目传送门

思路提供

由于题目中询问的是最小需要的查找次数，但是正常的二分查找是不满足我们这道题目的（标准的二分是自定义向下取整，但是没有考虑向上取整的情况），但是只要我们便利出每一种情况（即向上取整和向下取整）就可以了，而 DFS 作为一种暴力的算法，就能够有效的便利全部情况，这样的话，我们再在其中取出每一种情况的最小值就能有效地解决问题了。

AC code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,flag,ans=1e9;
int a[10000005];
void dfs(int cnt,int l,int r){
	if(l==r && a[l]==flag){
		ans=min(ans,cnt);//找到答案就记录ans的值
		return ;//不返回会导致死循环
	}
	else{
		int mid1=(l+r)>>1,mid2=(l+r+1)>>1;//这里要考虑向上和向下取整
		if(a[mid1]>=flag){
			dfs(cnt+1,l,mid1);
		}
		else{
			dfs(cnt+1,mid1+1,r);
		}
		if(a[mid2]-1>=flag){
			dfs(cnt+1,l,mid2-1);
		}
		else{
			dfs(cnt+1,mid2,r);
		}//与题目中随机化类似的判断，用来便利全部情况
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	cin>>m;//按照题意输入
	while(m--){
		scanf("%d",&flag);
		ans=1e9;//先将答案赋值为极大值，因为我们要取的是最小值
		dfs(0,1,n);
		cout<<ans<<endl;//换行符一定要留下
	}
	return 0;
}