binary search divide by 4

Question

Binary search divide array in 2 parts. But what if I want to divide the array in 4 parts ? Here is my approach

while (low <= h){ quartal = (low + high) / 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;

        }

that work but not for all values. can someone tell me what wrong with my approach?

Answer 1

In addition to what CodingTil has said.

You will have to do the following when doing your checks. Try to think of what would happen with edge cases like a length of 103 or just an array of [0,1]. In your code if we had an array length of 103, we would divide by 4 and get quartels of length 25.75. This can be problematic if we floor the quartel at the start as you'll miss out on values at index 101 and above. You'll have to adjust your other if statements in a similar manner.

    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

Your seventh if statement has an error (your eighth if statement will also have to be adjusted), it should read as follows. And I believe you'll be able to get rid of the ninth if statement altogether.

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;
}