Algorithm binary search (Based on divide and conquer) does not search well in a matrix

Question

Algorithm binary search (Based on divide and conquer) does not search well in a matrix

Navigation

#1 by (2 votes)

3

Good, I have created a code based on binary search, which makes recursive calls to find an Integer that is passed as a parameter (element). The problem is that when it comes to testing it (making it look for all the numbers contained in a matrix) it only finds me a few and making a triangle. (Look at image)

The code is as follows:

public boolean contiene(int[][] matriz, int elemento) {
    return encontrarNumero(matriz, 0, matriz.length-1, 0, matriz[0].length-1, elemento);
}

public boolean encontrarNumero(int[][] matriz, int f0, int fN, int c0, int cN, int elem){
    boolean enc= false;
    if(f0==fN && c0==cN){
        return (matriz[f0][cN]==elem);
    }
    if(f0 < fN || c0<cN){
        int fk = (f0+fN)/2;
        int ck = (c0+cN)/2;

        if(elem > matriz[fk][ck]) {
            //Busca en primer cuadrante
            enc = encontrarNumero(matriz, f0, fk, c0, ck, elem);
            //busca en el tercero
            enc = encontrarNumero(matriz, fk+1, fN, c0, ck, elem);
        }
        else if (elem < matriz[fk][ck]){
            //busca en el tercero
            enc = encontrarNumero(matriz, fk+1, fN, c0, ck, elem);
            //busca en el segundo
            enc = encontrarNumero(matriz, f0, fk,ck+1, cN, elem);
            //busca en el cuarto
            enc = encontrarNumero(matriz,fk+1, fN, ck+1, cN, elem);
        }
        else if(matriz[fk][ck]==elem){
            return true;
        }
    }
    return enc;
}

The idea would be to find all the numbers inside the cardboard (as proof), but it does not and it only finds a few.

The function that calls the contains is this:

for(int i=99; i>0; i--)
        if(cb.contiene(carton, i)){
            if(texto.length()>0) texto.append(", ");
            texto.append(i);
        }

Thank you very much. Greetings

java

asked by Varox 06.10.2017 в 10:39

source

1 answer

Linking multiple files Delete part of a set of tuples that form an array

score 2 · Accepted Answer

Your code has an error that once you know it will seem obvious: When you make the recursive call, you save the result in the boolean variable enc . But you forget to check it! What happens if you find the item in the first quadrant? Well, it will not be in the third quadrant and enc will change from true to false, "forgetting" that you have already found the element

//Busca en primer cuadrante
enc = encontrarNumero(matriz, f0, fk, c0, ck, elem); //enc==true
//busca en el tercero
enc = encontrarNumero(matriz, fk+1, fN, c0, ck, elem); //enc==false

So your algorithm only finds the numbers that are in the last place you look, because if you find them before, you keep looking.

Code that I used to make the test, based on your code and on the image that you have put (only stick I see your exposure of the problem, it is better to put text than an image):

public class Test {

    public static boolean contiene(int[][] matriz, int elemento) {
        return encontrarNumero(matriz, 0, matriz.length - 1, 0, matriz[0].length - 1, elemento);
    }

    public static boolean encontrarNumero(int[][] matriz, int f0, int fN, int c0, int cN, int elem) {
        boolean enc = false;
        if (f0 == fN && c0 == cN) {
            return (matriz[f0][cN] == elem);
        }
        if (f0 < fN || c0 < cN) {
            int fk = (f0 + fN) / 2;
            int ck = (c0 + cN) / 2;

            if (elem > matriz[fk][ck]) {
                // Busca en primer cuadrante
                enc = encontrarNumero(matriz, f0, fk, c0, ck, elem);
                // busca en el tercero
                enc = encontrarNumero(matriz, fk + 1, fN, c0, ck, elem) || enc;
            } else if (elem < matriz[fk][ck]) {
                // busca en el tercero
                enc = encontrarNumero(matriz, fk + 1, fN, c0, ck, elem) || enc;
                // busca en el segundo
                enc = encontrarNumero(matriz, f0, fk, ck + 1, cN, elem) || enc;
                // busca en el cuarto
                enc = encontrarNumero(matriz, fk + 1, fN, ck + 1, cN, elem)|| enc;
            } else if (matriz[fk][ck] == elem) {
                return true;
            }
        }
        return enc;
    }

    public static void main(String[] args) {
        int[][] carton = { 
                { 69, 57, 43, 28, 14 },
                { 68, 56, 35, 25, 13 },
                { 66, 55, 34, 22, 8 },
                { 64, 52, 32, 21, 7 },
                { 62, 47, 31, 17, 5 } };
        int[] buscados = { 62, 52, 34, 21, 7 };

        for (int b : buscados) {
            System.out.println("El número "+b+" está?: "+ contiene(carton, b));
        }
    }

}