Artigos Java Implementando uma busca binária normal e recursiva

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