Dúvida sobre ponto de inserção (método binarySearch)

Programação Java
#1

Pessoal, estou com uma dúvida neste código (pág 316 , cap7 da Kathy):

String [] sa = {"one", "two" , "three" , "four");

ReverseCompare rs = new ReverseCompare();

Arrays.sort(array, rs);

 System.out.println("binarysearch" + Arrays.binarySearch(array,"four"));

É retornado (no método Arrays.binarySearch)-1 pra “four” , 1 pra “three” , -5 pra “two” e -1 pra “one”.

Por que desses valores (não entendi aquela explicação do ponto de inserção, porque parece que retorna números aleatórios)?[/list][/list

#2

Para fazer o binarySearch, o array precisa estar ordenado, então é necessário fazer um sort antes, se vc não fizer, muito provavelmente ele não vai achar o elemento que vc quer e o resultado será indefinido. Quando vc faz da forma como esta fazendo (passando o array e a key), ele vai buscar usando a ordenação padrão, que nesse caso é a ordem alfabética dos elementos, mas o array não esta ordenado nessa ordem alfabética, vc ordenou usando outro Comparator, logo o resultado é indefinido tb. Para buscar de forma correta, vc deve passar ao binarySearch o comparator que vc usou para ordenar o array, no caso o rs, senão sim, o resultado não tem nada a ver com nada.

#3

Ok , entendi o que vc explicou . Mas no livro ele explica o valor de retorno de cada busca desordenada , ou seja , esses valores que parecem não ter nada a ver , na verdade tem uma explicação que não entendi … Entendeu minha dúvida ?

#4

É o ponto de inserção, onde a key que vc procura deveria estar no array. Na busca binaria ele vai de cara no meio do array, compara esse elemento do meio com a key que vc quer (no seu exemplo esse elemento é o ‘three’, por isso ele acha pois é a primeira comparação que ele faz), verifica qual a posição relativa da sua key com esse elemento, se ela deveria estar depois então avança para a metade da metade final do array, se sua key deveria estar antes, então avança para a metade da primeira metade do array, e ai refaz o processo sempre limitando o tamanho da busca pela metade, até que chega uma hora que não da mais para repartir, a key que vc procura deveria estar ali, é esse ponto que ele retorna.
ps: se não entendeu ainda depois posto algo com exemplo se quiser.

#5

Ah, e neste seu exemplo, vc vai ter sempre valores nos extremos (-1 ou -array.length). Por que? ex: o lugar onde iria inserir i em um array com a,b,m,r,t,x ordenado de forma reversa: x,t,r,m,b,a, o i deveria (segundo a comparação default de string) estar a esquerda do elemento do meio: r, então a busca parte para analisar a primeira metade do array, e como todos elementos dessa primeira metade viriam depois de i (na comp default), o i deveria sempre estar antes de deles (dai o -1 significando que ele deveria ser o primeiro). A mesma lógica vale para o contrario, vc tentar incluir z, ele deveria estar na parte final da lista, mas essa parte só tem elementos que deveriam estar antes de z, por isso ele retorna que z deveria ser o ultimo.

#6

Continuo sem entender … Vc poderia explicar em cima do meu exemplo o porquê de :

-1 pra “four” , 1 pra “three” , -5 pra “two” e -1 pra “one” ?

#7

[quote=“bigwaves”]Continuo sem entender … Vc poderia explicar em cima do meu exemplo o porquê de :

-1 pra “four” , 1 pra “three” , -5 pra “two” e -1 pra “one” ?[/quote]

Puts eu não queria usar teu exemplo justamente porque é mais difícil de entender pois é um array de poucos elementos. É mais fácil de entender a comparação entre letras, bem como o conceito de busca em arvores em um array grande (da para enxergar melhor a divisão na metade). Fora que eu não gosto de usar exemplos dados pela pessoa que pergunta, porque ai eu obrigo ela a pensar um pouco, dando outro exemplo e fazendo com que ela tire as próprias conclusões encima do exemplo que ela deu (faz com que a pessoa tenha que entender)

Mas, vamos la então, seu array inicial é esse:

"one", "two", "three", "four"

depois que você ordenou de forma inversa ele ficou assim:

"two", "three", "one", "four"

beleza?

Ai você mandou fazer uma busca binária pelo “four” nesse array. Você não passou a forma como o array esta ordenado (o Comparator usado), logo a busca vai pensar que esta ordenado de maneira default (pelo Comparable, que no caso de String é a ordem alfabética).

A busca binária divide o array no meio, compara o elemento do meio com a key que vc quer procurar e verifica se essa key deveria estar depois ou antes desse elemento com base no Comparator passado por parâmetro ou na forma como Comparable esta implementado.

Então, o primeiro intervalo de busca no array vai da posição 0 (“two”) até a posição 3 (“four”), ou seja de 0 até 3, qual a metade disso? 1,5 então arredondando a posição 1 é a metade do seu intervalo de busca. Pega esse elemento da metade (“three”), e compara com o elemento que você quer procurar (“four”), porem a busca vai comparar pela ordem alfabética (como Comparable de string esta implementado e não pelo Comparator real que o array esta ordenado). Ou seja, essa comparação vai dizer que o “four” deveria estar ANTES do “three” (pois “four” ‘F’ vem antes de “three” ‘T’ quando ordenado de forma alfabética), logo a busca vai desconsiderar o que tem depois de “three” (pois “four” tem que vir antes de “three”, então de “three” em diante ele NÃO pode estar, de acordo com a comparação usada), logo ele vai fazer a mesma analise só que ao invés de considerar o array inteiro (posição 0 - 3) a busca vai considerar só a primeira metade, que é onde “four” tem que estar: posição 0 até metade da busca anterior menos 1, ou seja da posição 0 até a posição 0. E ai o processo reinicia, qual a metade desse intervalo? É a posição 0, o que tem nessa posição? “two”. A comparação de “two” com “four” diz que “four” deveria estar ANTES de “two”, logo vai procurar na metade anterior ou seja, da posição 0 até metade da busca anteior menos 1, ou seja posição 0 até -1 , mas ai não faz sentido, como procurar de 0 até -1? Logo a conclusão é que ele não conseguiu achar a key e que ela deveria estar na posição “de” do intervalo que estou buscando (que é a posição 0).

Pois é, mas array tem posição 0, então não posso retornar essa posição para o usuário pois ele não vai saber se estou falando da posição 0 que achou ou na posição 0 que deveria estar. Para isso eu utilizo valores negativos para dizer onde o elemento key deveria estar, mas ao invés de começar por 0, eu começo por -1, ou seja, -1 significa que o elemento key deveria estar na posição 0 do array, -2 = posição 1, -3 = posição 2 e assim por diante.

É dai que ele chega ao valor -1 para o “four”

O caso de buscar “three”, por sorte ele acha, pois quando ele divide o array pela primeira vez (metade da busca entre o intervalo 0 até 3 = 1), o elemento do meio é o “three”, sendo assim ele acha logo de cara e retorna sua posição 1

O caso do “one” é identifico do “four”, na primeira divisão ele compara “one” com “three” e determina que “one” deveria estar antes. Depois mesma coisa na comparação com “two”, logo no fim deveria estar na posição 0 (retornando assim -1).

O caso do “two” é identifico também, mas quando ele faz a primeira comparação com “three”, essa comparação diz que “two” deveria estar DEPOIS, então o intervalo de busca que antes era 0 até 3 agora é metade da busca anterior mais 1 até 3, ou seja posição 2 até 3, ignorando a primeira metade do array. Divide o novo intervalo de busca ao meio, e reinicia o processo. Essa divisão vai dizer que o meio é a posição 2 (“one”), ele compara “one” com “two” e a comparação diz que “two” deveria estar DEPOIS de “one”, então o novo intervalo de busca é de novo a metade da busca anterior mais 1 até 3, ou seja da posição 3 até 3, compara “two” com “four” e a comparação também diz que tem que estar depois, mesmo esquema, o novo intervalo de busca é metade da busca anterior mais 1 até 3, ou seja posição 4 ate 3, mas ai chega de novo a algo sem sentido, como buscar da posição 4 - 3? Logo a busca chega a conclusão que não achou a key e diz que ela deveria estar na posição 4, ou seja -5 se for colocar de forma negativa.

Bem, é isso, se você ainda assim não entender, não adianta eu continuar falando, aconselho que estude arvores binárias, busca em arvores binárias, bem como o algoritmo implementado pelo Arrays.binarySearch (que por sinal é bem simples), e também estude um pouco as interfaces Comparator e Comparable.

Beleza?

#8