Veja nesta dica como implementar busca binária em Java.
Busca binária
public class BinarySearch
{
public static final int NOT_FOUND = -1;
/**
*@returnposiçãoonde o item foi encontrado, ou não.
*/
public static int binarySearch(Comparable[]a, Comparablex)
{
int low = 0;
int high = a.length-1;
int mid;
while(low <= high)
{
mid=(low + high) / 2;
if(a[mid].compareTo(x) < 0)
low = mid + 1;
elseif(a[mid].compareTo(x) > 0)
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];
for(int i=0;ia[i] = new Integer(i*2);
for(int i=0;iSystem.out.println("Encontrado"+i+"em"+binarySearch(a,newInteger(i)));
}
}
Busca binária recursiva
public class BinarySearchRecursive
{
public static final int NOT_FOUND = -1;
/**
*@returnposição onde o item foi encontrado ou não encontrado.
*/
public static int binarySearch(Comparable[]a,Comparablex)
{
return binarySearch(a,x,0,a.length-1);
}
/**
*recursão
*/
private static int binarySearch(Comparable[]a,Comparablex,int low,int high)
{
if(low > high)
returnNOT_FOUND;
int mid = (low + high) / 2;
if(a[mid].compareTo(x) < 0)
return binarySearch(a,x,mid+1,high);
elseif(a[mid].compareTo(x) > 0)
return binarySearch(a,x,low,mid-1);
else
return mid;
}
//Programa teste
public static void main(String[]args)
{
int SIZE = 8;
Comparable[]a = new Integer[SIZE];
for(inti=0;ia[i]=new Integer(i*2);
for(int i=0;iSystem.out.println("Encontrado"+i+"em"+binarySearch(a,newInteger(i)));
}
}
public class BinarySearch
{
public static final int NOT_FOUND = -1;
/**
*@returnposiçãoonde o item foi encontrado, ou não.
*/
public static int binarySearch(Comparable[]a, Comparablex)
{
int low = 0;
int high = a.length-1;
int mid;
while(low <= high)
{
mid=(low + high) / 2;
if(a[mid].compareTo(x) < 0)
low = mid + 1;
elseif(a[mid].compareTo(x) > 0)
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];
for(int i=0;ia[i] = new Integer(i*2);
for(int i=0;iSystem.out.println("Encontrado"+i+"em"+binarySearch(a,newInteger(i)));
}
}
Busca binária recursiva
public class BinarySearchRecursive
{
public static final int NOT_FOUND = -1;
/**
*@returnposição onde o item foi encontrado ou não encontrado.
*/
public static int binarySearch(Comparable[]a,Comparablex)
{
return binarySearch(a,x,0,a.length-1);
}
/**
*recursão
*/
private static int binarySearch(Comparable[]a,Comparablex,int low,int high)
{
if(low > high)
returnNOT_FOUND;
int mid = (low + high) / 2;
if(a[mid].compareTo(x) < 0)
return binarySearch(a,x,mid+1,high);
elseif(a[mid].compareTo(x) > 0)
return binarySearch(a,x,low,mid-1);
else
return mid;
}
//Programa teste
public static void main(String[]args)
{
int SIZE = 8;
Comparable[]a = new Integer[SIZE];
for(inti=0;ia[i]=new Integer(i*2);
for(int i=0;iSystem.out.println("Encontrado"+i+"em"+binarySearch(a,newInteger(i)));
}
}
public class BinarySearchRecursive
{
public static final int NOT_FOUND = -1;
/**
*@returnposição onde o item foi encontrado ou não encontrado.
*/
public static int binarySearch(Comparable[]a,Comparablex)
{
return binarySearch(a,x,0,a.length-1);
}
/**
*recursão
*/
private static int binarySearch(Comparable[]a,Comparablex,int low,int high)
{
if(low > high)
returnNOT_FOUND;
int mid = (low + high) / 2;
if(a[mid].compareTo(x) < 0)
return binarySearch(a,x,mid+1,high);
elseif(a[mid].compareTo(x) > 0)
return binarySearch(a,x,low,mid-1);
else
return mid;
}
//Programa teste
public static void main(String[]args)
{
int SIZE = 8;
Comparable[]a = new Integer[SIZE];
for(inti=0;ia[i]=new Integer(i*2);
for(int i=0;iSystem.out.println("Encontrado"+i+"em"+binarySearch(a,newInteger(i)));
}
}
