Comment

dingchenkai: 2024-10-09 19:41:15

二分区间为[l,mid-1] 和 [mid + 1,r]

OverSky: 2023-10-04 18:13:10

//“父亲”的身份究竟是什么，相信大家都很好奇，下面就让小编带大家一起了解吧。

#include <iostream>
using namespace std;

const int n = 20000+5;
int num[n];

int main() {
	int M,N,X;
	cin>>M;

	while(M--) {
		cin>>N>>X;
		for(int i = 0; i<N; ++i) {
			cin>>num[i];
		}

		int l=0, r=N-1;
		int pre_mid = N,mid;

		while(l <= r) {
			pre_mid = mid;    //记录父节点索引
			mid = l + (r - l)/2;
			if(num[mid] == X) {
				break;
			} else if(num[mid] > X) {
				r = mid - 1;
			} else {
				l = mid +1;
			}

		}
		
		if(num[mid] == X) cout<<"success, father is "<<num[pre_mid]<<endl;
		else cout<<"not found, father is "<<num[mid]<<endl;
	}
	return 0;
}
//看了今天的内容，大家有什么想法呢？欢迎在评论区告诉小编一起讨论哦。

syl616: 2023-04-21 00:52:16

#include<iostream>
using namespace std;
bool search(int start, int end, int*& p,int k)
{
	
	if (start > end)
	{
		return 0;
	}
	else if (start == end)
	{
		
		return p[start]==k;
	}
	else if(p[(start + end) / 2] == k)
	{
		
		return 1;
	}
	else if (p[(start + end) / 2] > k)
	{
	

		search(start, (start + end) / 2 - 1, p, k);
	}
	else
	{
	
		search((start + end) / 2+1,end, p, k);
	}
}
int searchfather(int start, int end, int*& p, int k,int father)
{

	if (start > end)
	{
		return 	p[start];
	}
	else if (start == end)
	{
		if (p[start] == k)
		{
			return p[father];
		}
		else
		{
		
			return p[start];

		}
		
	}
	else if (p[(start + end) / 2] == k)
	{
		return p[father];
	}
	else if (p[(start + end) / 2] > k)
	{

		searchfather(start, (start + end) / 2 - 1, p, k, (start + end) / 2);
	}
	else
	{

		searchfather((start + end) / 2 + 1, end, p, k,(start + end) / 2  );
	}
}
int main()
{
	int time = 0; int key = 0; int num = 0;
	cin >> time;
	for (int i = 0; i < time; i++)
	{
		cin >> num;
		cin >> key;
		int* data = new int[num + 1];
		for (int i = 1; i <= num; i++)
		{
			cin >> data[i];
		}
		if (search(1, num, data, key))
		{
			cout << "success, father is " << searchfather(1, num, data, key, num+1) << endl;
		}
		else
		{
			cout << "not found, father is " << searchfather(1, num, data, key, num+1) << endl;
		}

	}
}

212071吴东冬: 2021-10-08 00:47:03

mid=low+(high-low)/2
@09019105

09019105王璟: 2021-05-01 01:19:50

mid=(low+high)/2不是会溢出吗，所以这样写会runtime error。请问要怎么调整呢？
int BinarySearch(int n) {
	int low = 1;
	int high = n;
	while (low <= high) {
		mid = (low + high) / 2;
		if (A[mid] == x) {
			return mid;
		}
		else if (A[mid] <x) {
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}
	}
	return -1;
}
救救我救救我

ding zhechen: 2020-12-22 11:02:04

哪位兄弟知道二分搜索输出父节点的具体情况？比如如果第一次搜索就找到需要的值，那么它的父节点是什么呢？

landscape: 2020-12-05 12:19:26

ａ