在几乎排序的数组中搜索

Question

给定一个非负整数数组，例如：

1. 除了数组可以用零填充外，所有元素都已排序
2. 最多有k个连续零
3. 如果我们把所有的零都去掉，我们得到排序的正整数数组

例子 3 0 0 4 7 9 0 0 0 0 11 15 0 19 20 0 0 31 40 0

对于 k=4

如果 k 是常数但我们不知道，我们需要函数 kAlmostSearch(int[] a, int num)。

我正在尝试修改二分搜索，但不确定我到底该怎么做。

我的目标是找到最有效的时间+空间方式来做。

Answer 1

您可以使用滑动窗口策略来调整二分查找以解决最多 k 个连续零的存在。目标是对这个更新后的数组执行二进制搜索，使用每个大小为 (k+1) 的窗口作为单个元素。

如何将这个策略付诸实践如下：

1. 初始化两个指针，left和right，分别指向数组的开始和结束。
2. 当左指针小于或等于右指针时： A。计算当前窗口的中间索引如下： 让 m = (左 + 右) / 2 如果 k > 0，按如下方式调整 m： 如果 a[m] == 0，则设置 m = min(m + k, right) 如果 a[m] != 0，则设置 m = max(m - k, left) b.如果 a[m] == num，返回 m。 C。如果 a[m] < num, set left = m + 1. d. If a[m] > num, 设右 = m - 1.
3. 如果没有找到num，返回-1。

说明：

我们为每次二分搜索迭代计算当前窗口的中间索引。如果中间元素为零，中间索引将更改为向右跳过最多 k 个连续零。这是因为数组在存在最多 k 个连续零的情况下并不是严格递增的，我们必须在搜索中考虑到这一点。

与此类似，如果中间元素不为零，我们将中间索引更改为向左跳过最多 k 个连续零。这是因为出现在非零元素左侧的任何零必须是最大允许的 (k+1) 个连续零的一部分。

我们通过将每个大小为 (k+1) 的窗口视为单个元素，保证二分查找方法在 O(log n) 时间内继续执行，即使数组中有多达 k 个连续的零。

对于 py 中的 ex

def kAlmostSearch(a, num):
    n = len(a)
    left, right = 0, n - 1
    k = 4  # example value, can be any non-negative integer
    
    while left <= right:
        m = (left + right) // 2
        
        # Adjust middle index to skip over up to k sequential zeroes
        if k > 0 and a[m] == 0:
            m = min(m + k, right)
            while m < right and a[m] == 0:
                m += 1
        elif k > 0 and a[m] != 0:
            m = max(m - k, left)
            while m > left and a[m] == 0:
                m -= 1
        
        if a[m] == num:
            return m
        elif a[m] < num:
            left = m + 1
        else:
            right = m - 1
    
    return -1