Implementando uma busca binária normal e recursiva

Você precisa estar logado para dar um feedback. Clique aqui para efetuar o login
Para efetuar o download você precisa estar logado. Clique aqui para efetuar o login
Confirmar voto
0
 (0)  (0)

Veja nesta dica como implementar busca binária em Java.

 

Veja nesta dica como implementar busca binária em Java.

 

 

1) Busca binária

 

public class BinarySearch
{
    public static final int NOT_FOUND = -1;
    
    /**
     @return posição onde o item foi encontrado, ou não.
     
*/
    public static int binarySearch( Comparable [ ] a, Comparable x )
    {
        int low = 0;
        int high = a.length - 1;
        int mid;

        while( low <= high )
        {
            mid = ( low + high ) / 2;

            if( a[ mid ].compareTo( x ) < )
                low = mid + 1;
            else if( a[ mid ].compareTo( x ) > )
                high = mid - 1;
            else
                return mid;
        }

        return NOT_FOUND;     // NOT_FOUND = -1
    }

    // Testando o programa
    public static void main( String [ ] args )
    {
        int SIZE = 8;
        Comparable [ ] a = new Integer [ SIZE ];
        forint i = 0; i < SIZE; i++ )
            a[ i ] = new Integer( i * );

        forint i = 0; i < SIZE * 2; i++ )
            System.out.println( "Encontrado " + i + " em " +
                                 binarySearch( a, new Integer( i ) ) );

    }
}

 

2) Busca binária recursiva

 

public class BinarySearchRecursive
{
    public static final int NOT_FOUND = -1;

    /**
     @return posição onde o item foi encontrado ou não encontrado.
     
*/
    public static int binarySearch( Comparable [ ] a, Comparable x )
    {
        return binarySearch( a, x, 0, a.length -);
    }

    /**
     * recursão
     */
    private static int binarySearch( Comparable [ ] a, Comparable x,
                                     int low, int high )
    {
        if( low > high )
            return NOT_FOUND;

        int mid = ( low + high ) / 2;

        if( a[ mid ].compareTo( x ) < )
            return binarySearch( a, x, mid + 1, high );
        else if( a[ mid ].compareTo( x ) > )
            return binarySearch( a, x, low, mid - );
        else
            return mid;
    }

    // Programa teste
    public static void main( String [ ] args )
    {
        int SIZE = 8;
        Comparable [ ] a = new Integer [ SIZE ];
        forint i = 0; i < SIZE; i++ )
            a[ i ] = new Integer( i * );

        forint i = 0; i < SIZE * 2; i++ )
            System.out.println( "Encontrado " + i + " em " +
                                     binarySearch( a, new Integer( i ) ) );
    }
}

 
Você precisa estar logado para dar um feedback. Clique aqui para efetuar o login
Receba nossas novidades
Ficou com alguma dúvida?