C++二分算法：找到最接近目标值的函数值

本文涉及的基础知识点

二分查找算法合集

题目

Winston 构造了一个如上所示的函数 func 。他有一个整数数组 arr 和一个整数 target ，他想找到让 |func(arr, l, r) - target| 最小的 l 和 r 。
请你返回 |func(arr, l, r) - target| 的最小值。
请注意， func 的输入参数 l 和 r 需要满足 0 <= l, r < arr.length 。

示例 1：
输入：arr = [9,12,3,7,15], target = 5
输出：2
解释：所有可能的 [l,r] 数对包括 [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]]， Winston 得到的相应结果为 [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0] 。最接近 5 的值是 7 和 3，所以最小差值为 2 。
示例 2：
输入：arr = [1000000,1000000,1000000], target = 1
输出：999999
解释：Winston 输入函数的所有可能 [l,r] 数对得到的函数值都为 1000000 ，所以最小差值为 999999 。
示例 3：
输入：arr = [1,2,4,8,16], target = 0
输出：0
参数范围：
1 <= arr.length <= 10^5
1 <= arr[i] <= 10^6
0 <= target <= 10^7

方法一超时

按二进制的位讨论

对任意一个二进制位，从左到右，出现第一个0之前是1，之后是0。我们用vIndexs记录各二进制位0的索引。
两层循环，第一层循环枚举起始l，第二层循环枚举各位。只需要考虑有二进位第一个变成0的位。

时间复杂度

O(nlogmax(logn+logm)) 约O(3e7) 处于超时边缘。

核心代码

class Solution {
public:
	int closestToTarget(vector<int>& arr, int target) {
		m_c = arr.size();
		const int iBitNum = 21;
		vector<vector<int>> vIndexs(iBitNum);
		for (int i = 0; i < m_c; i++)
		{
			for (int j = 0; j < iBitNum; j++)
			{
				if (arr[i] & (1 << j))
				{
					continue;
				}
				vIndexs[j].emplace_back(i);
			}
		}
		int iRet = INT_MAX;
		for (int l = 0; l < m_c; l++)
		{
			set<int> setIndexs ;
			for (int j = 0; j < iBitNum; j++)
			{
				auto it = std::lower_bound(vIndexs[j].begin(), vIndexs[j].end(), l);
				if (vIndexs[j].end() != it)
				{
					setIndexs.emplace(*it);
				}
			}
			vector<int> vValue = { arr[l] };
			for (const auto& index : setIndexs)
			{
				vValue.emplace_back(vValue.back() & arr[index]);
			}
			for (const auto& value : vValue)
			{
				iRet = min(iRet, abs(value - target));
			}
		}
		return iRet;
	}
	int m_c;
};

测试用例

template <class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template <class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}
}

int main()
{
	vector<int> arr;
	int target;
	int res;
	{
		Solution slu;		
		arr = { 9, 12, 3, 7, 15 };
		int target = 5;
		res = slu.closestToTarget(arr, target);
		 Assert(2, res);
	}
	{
		Solution slu;
		arr = { 1000000,1000000,1000000 };
		int target =1;
		res = slu.closestToTarget(arr, target);
		Assert(999999, res);
	}
	{
		Solution slu;
		arr = { 1,2,4,8,16 };
		int target = 0;
		res = slu.closestToTarget(arr, target);
		Assert(0, res);
	}



	//CConsole::Out(res);

}

方法二：超时

分析

从右向左枚举左边缘，setIndexs 记录各位为0的最小索引，vPre记录本位的上一个索引方便删除。

时间复杂度

O(nlogmax(loglogmax)+nlogmax)

核心代码

class Solution {
public:
	int closestToTarget(vector<int>& arr, int target) {
		m_c = arr.size();
		const int iBitNum = 21;
		vector<int> vPre(iBitNum, -1);
		multiset<int> setIndexs;
		int iRet = INT_MAX;
		for (int left = m_c - 1; left >= 0; left--)
		{
			for (int iBit = 0; iBit < iBitNum; iBit++)
			{
				if (arr[left] & (1 << iBit))
				{
					continue;
				}
				if (-1 != vPre[iBit])
				{
					setIndexs.erase(setIndexs.find(vPre[iBit]));
				}
				setIndexs.emplace(left);
				vPre[iBit] = left;
			}

			vector<int> vValue = { arr[left] };
			for (const auto& index : setIndexs)
			{
				vValue.emplace_back(vValue.back() & arr[index]);
			}
			for (const auto& value : vValue)
			{
				iRet = min(iRet, abs(value - target));
			}
		}
		return iRet;
	}
	int m_c;
};

方法三：

分析

func(arr,l,r)等于arr[l]&func(arr,l+1,r)。
令iMax=max(nums[i]) ，func(arr,l,x) x取值范围[l,n) 最多只有log(iMax)种可能。nums[i]最多有log(iMax)个二进制位为1,and只会将1变成0，不会将0变成1。所以1只会不断减少，最坏的情况下，每次减少一个1，共减少log(iMax)次。

时间复杂度

O(nlogmaxloglogmax)。稳定能过。

class Solution {
public:
	int closestToTarget(vector<int>& arr, int target) {
		m_c = arr.size();	
		set<int> setPre = { arr.back() };
		int iRet = abs(arr.back() - target);
		for (int left = m_c - 1-1; left >= 0; left--)
		{
			set<int> dp = { arr[left] };
			for (const auto& pr : setPre)
			{
				dp.emplace(pr & arr[left]);
			}
			setPre.swap(dp);
			for (const auto& pr : setPre)
			{
				iRet = min(iRet, abs(pr - target));
			}
		}
		return iRet;
	}
	int m_c;
};

方法四

分析

dp本来就是降序，所有用向量也可以判断是否重复，换成向量速度再次提升。理论上速度可以提升几倍，实际提升50%左右。

时间复杂度

O(nlogmax)。

class Solution {
public:
	int closestToTarget(vector<int>& arr, int target) {
		m_c = arr.size();	
		vector<int> vPre = { arr.back() };
		int iRet = abs(arr.back() - target);
		for (int left = m_c - 1-1; left >= 0; left--)
		{
			vector<int> dp = { arr[left] };
			for (const auto& pr : vPre)
			{
				const int iNew = pr & arr[left];
				if (dp.back() != iNew)
				{
					dp.emplace_back(iNew);
				}
			}
			vPre.swap(dp);
			for (const auto& pr : vPre)
			{
				iRet = min(iRet, abs(pr - target));
			}
		}
		return iRet;
	}
	int m_c;
};

2023年3月第一版

class Solution {
public:
int closestToTarget(vector& arr, int target) {
std::set pre;
std::priority_queue queNear;
for (const auto& a : arr)
{
std::set dp;
for (const auto& pr : pre)
{
dp.insert(pr&a);
queNear.push(abs((pr&a)-target));
if (queNear.size() > 1)
{
queNear.pop();
}
}
dp.insert(a);
queNear.push(abs(a-target));
if (queNear.size() > 1)
{
queNear.pop();
}
pre.swap(dp);
}
return queNear.top();
}
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653