Oi pessoal, boa noite, tudo bem?
Tenho uma tarefa aqui da faculdade pra fazer e queria a ajuda,dicas e a opinião de vocês sobre o desenvolvimento dessa tarefa.
Transformar o seguinte método
em um método recursivo. (Sem alterar a assinatura)
public int BinarySearch (int a[], int key)
{
int inf, sup, med;
inf = 0; sup = a.length -1;
while (inf <= sup ){
med = (inf + sup)/2; //divisão inteira
if(key == a[med]) return med;
else if(key > a[med]) inf = med + 1; //procura na segunda metade
else if(key < a[med]) sup = med - 1; //procura na primeira metade
}
return -1;
}
Tive ajuda de um colega aqui e chegamos no seguinte:
public int BinarySearch (int a[], int key){
return BinarySearchR(a, key, 0, a.length - 1);
}
public int BinarySearchR (int a[], int key, int first, int last){
int emp = (first + last) / 2;
if(key == a[first])
return first; /*se a chave é igual a primeira posição do array,
retorna o valor armazenado na primeira. */`
else if(key == a[last])
return last; /* senão se, a chave é igual a ultima posição,
retorna o valor armazenado na ultima */
else if(key < a[first] || key > a[last] || emp < 0 || emp > a.length -1)
return -1; /*senão se a chave é menor que a primeira posição do array OU
a chave é maior que a ultima posição do array OU
o "emp" é menor que zero OU
o "emp" é maior que o comprimento do array
(emp = valor do primeiro + valor do ultimo ultimo dividido por 2) */
else if(key == a[emp])
return emp; /* senão se a chave tem o mesmo valor que "emp",
retorna o valor de "emp" */
else if(key < a[emp])
return BinarySearchR(a, key, first, emp - 1);
/* senão se a chave é menor que "emp"
retorna o array, a chave, a primeira posição do array
e o valor de "emp" - 1 */
else if(key > a[emp])
return BinarySearchR(a, key, emp + 1, last);
/* senão se a chave é maior que "emp"
retorna o array, a chave, o valor de "emp" + 1,
e, a ultima posição do array */
else
return -1; //senão retorna -1
}
Meus comentários no código estão corretos? Poderiam melhorar? Obrigado
