假设一个数组只包含两种元素，如何快速找到它们的边界？
Suppose an array contains only two kinds of elements, how to quickly find their boundaries?
之前问过，这次不一样
由于我们的数组只有两个元素，所以不妨设置为1和-1，其中1在数组左边，-1在数组右边：
[1,...,1,1,-1,-1,...,-1]
1和-1同时存在，1和-1的个数不一定相同。还有，1和-1的个数都很大
然后，定义1和-1的分界线为-1最接近的index。例如，对于以下数组：
[1,1,1,-1,-1,-1,-1]
它的边界是3。
现在，对于数组中的每个数字，我用一个设备覆盖它，你必须解锁才能看到其中的数字。
我想尝试解锁尽可能少的覆盖 1 的设备，因为看到“1”所花的时间比看到“-1”所花的时间长得多。而且我也想尽可能的减少我的时间成本.
如何搜索才能尽快得到边界？
这个问题很像“鸡蛋掉落”问题，但是错误的猜测有很大的固定成本 (100)，而正确的猜测有很小的成本 (1)。
假设边界的每个可能位置是，让 E(n) 成为找到数组中最右边 1 的索引（或发现数组全为 -1）的（最佳）预期成本同样可能。如果数组全为-1，定义最右边1的索引为-1。
如果您选择查看索引 i 处的数组元素，则它是 -1 的概率是 i/(n+1)，1 的概率是 (n-i+1)/(n+1)。
因此，如果您查看数组元素 i，找到边界的预期成本是 (1+E(i)) * i/(n+1) + (100+E(n-i-1)) * (n-i+1)/(n+1)。
因此E(n) = min((1+E(i)) * i/(n+1) + (100+E(n-i-1)) * (n-i+1)/(n+1), i=0..n-1)
对于每个 n，使方程最小化的 i 是该长度数组的最佳数组元素。
我不认为你可以解析地解决这些方程，但你可以在 O(n^2) 时间内用动态规划解决它们。
解决方案看起来像是对大 n 的非常倾斜的二进制搜索。对于较小的n，它会倾斜很多，以至于它会从右边开始遍历。
如果我是对的，最小化成本预期的策略是在有利于 -1 结果的区间的一小部分绘制，与成本成反比。因此，与其选择中间指数，不如选择正确的百分位数。
但这仍然对应一个对数渐近复杂度。
对于最坏的情况，您可能无能为力。
之前问过
由于我们的数组只有两个元素，所以不妨设置为1和-1，其中1在数组左边，-1在数组右边：
[1,...,1,1,-1,-1,...,-1]
1和-1同时存在，1和-1的个数不一定相同。还有，1和-1的个数都很大
然后，定义1和-1的分界线为-1最接近的index。例如，对于以下数组：
[1,1,1,-1,-1,-1,-1]
它的边界是3。
现在，对于数组中的每个数字，我用一个设备覆盖它，你必须解锁才能看到其中的数字。
我想尝试解锁尽可能少的覆盖 1 的设备，因为看到“1”所花的时间比看到“-1”所花的时间长得多。而且我也想尽可能的减少我的时间成本.
如何搜索才能尽快得到边界？
这个问题很像“鸡蛋掉落”问题，但是错误的猜测有很大的固定成本 (100)，而正确的猜测有很小的成本 (1)。
假设边界的每个可能位置是，让 E(n) 成为找到数组中最右边 1 的索引（或发现数组全为 -1）的（最佳）预期成本同样可能。如果数组全为-1，定义最右边1的索引为-1。
如果您选择查看索引 i 处的数组元素，则它是 -1 的概率是 i/(n+1)，1 的概率是 (n-i+1)/(n+1)。
因此，如果您查看数组元素 i，找到边界的预期成本是 (1+E(i)) * i/(n+1) + (100+E(n-i-1)) * (n-i+1)/(n+1)。
因此E(n) = min((1+E(i)) * i/(n+1) + (100+E(n-i-1)) * (n-i+1)/(n+1), i=0..n-1)
对于每个 n，使方程最小化的 i 是该长度数组的最佳数组元素。
我不认为你可以解析地解决这些方程，但你可以在 O(n^2) 时间内用动态规划解决它们。
解决方案看起来像是对大 n 的非常倾斜的二进制搜索。对于较小的n，它会倾斜很多，以至于它会从右边开始遍历。
如果我是对的，最小化成本预期的策略是在有利于 -1 结果的区间的一小部分绘制，与成本成反比。因此，与其选择中间指数，不如选择正确的百分位数。
但这仍然对应一个对数渐近复杂度。
对于最坏的情况，您可能无能为力。