二分查找除以 4

Question

二进制搜索将数组分成两部分。但是，如果我想将数组分成 4 个部分怎么办？这是我的方法

同时（低 <= h）{ 四分之一=（低+高）/ 4；

        if (array[quartal] == x) return quartal;
        if (array[2*quartal] == x) return 2*quartal;
        if (array[3*quartal] == x) return 3*quartal;
        if (array[4*quartal] == x) return 4*quartal;

        if (array[quartal] > x) high = quartal-1;
        if (array[quartal] < x && array[2*quartal] > x){
            low = quartal + 1;
            high = 2*quartal-1;
        }
        if (array[2*quartal] < x && array[3*quartal] > x){
            low = quartal + 1;
            high = 2*quartal -1;
        }
        if (array[3*quartal] < x && array[4*quartal] > x){
            low = 2*quartal + 1;
            high = 3*quartal -1;
        }
        if (array[4*quartal] < x){
            low = 3*quartal + 1;

        }

有效但不适用于所有值。有人可以告诉我我的方法有什么问题吗？

Answer 1

回答你的问题：

你的数组排序了吗？二进制搜索仅适用于排序数组。
在最后一个 if 语句中，您检查是否 array[4*quartal] < x。请注意，这可能会导致错误，因为 quartal 是一个整数，因此 4*quartal 将不等于 (low + high)，而是 4*floor((low+high)/4)。因此，根据 (low+heigh) 是否是 4.

因为 4*quartal 应该是您正在搜索的数组中的段的结尾，所以我建议将 4*quartal 替换为 (low+high)。

希望对您有所帮助。

Answer 2

除了 CodingTil 所说的。

您在进行检查时必须执行以下操作。试着想一想像长度为 103 或 [0,1] 数组这样的边缘情况会发生什么。在您的代码中，如果我们的数组长度为 103，我们将除以 4 并得到长度为 25.75 的四分位数。如果我们在一开始就对四分位数进行下限，这可能会出现问题，因为您会错过索引 101 及以上的值。您必须以类似的方式调整其他 if 语句。

    if (array[floor(quartal)] == x) return floor(quartal);
    if (array[floor(2*quartal)] == x) return floor(2*quartal);
    if (array[floor(3*quartal)] == x) return floor(3*quartal);
    if (array[high] == x) return high; // should be a whole number so no need to round

你的第七个if语句有错误（你的第八个if语句也需要调整），应该是这样的。而且我相信您将能够完全摆脱第九个 if 语句。

if (array[floor(2*quartal)] < x && array[floor(3*quartal)] > x){
    low = floor(2*quartal) + 1;
    high = floor(3*quartal) -1;
}

// high remains unchanged, as we are in the highest quartal
if (array[floor(3*quartal)] < x && array[floor(4*quartal)] > x){
    low = floor(3*quartal) + 1;
}

二分查找除以 4

binary search divide by 4

java

binary-search