Dúvida no método binarySearch

JavaTeenager Membro desde: 09/02/2008 01:12:58 Mensagens: 189 Offline

Tanto o ArrayList, como o LinkedList geram como saída 1 (pois o elemento "a" está na segunda posição da lista).

Porém, estava fazendo essa questão aqui:

A) 0
B) 1
C) 2
D) a
E) b
F) c
G) The result is undefined

A resposta correta é a G, mas eu iria de B. Por que a B não é sempre correta? Existe alguma implementação de List que não coloca seus elementos um atrás do outro?

Obrigado!

GUJ Hacker Membro desde: 26/09/2009 09:18:56 Mensagens: 5750 Offline

List != Set

List deixa os elementos na ordem em que foram inseridos ("ordered"), não arrumados ("sorted").

Como binarySearch só funciona corretamente se os elementos estiverem arrumados ("sorted"), então a resposta é G.

JavaTeenager Membro desde: 09/02/2008 01:12:58 Mensagens: 189 Offline

entanglement wrote:List != Set

List deixa os elementos na ordem em que foram inseridos ("ordered"), não arrumados ("sorted").

Como binarySearch só funciona corretamente se os elementos estiverem arrumados ("sorted"), então a resposta é G.

Eu entendo isso, mas no caso da sequência b a c sempre o BinarySearch irá funcionar, pois ele vai acabar pegando o elemento do meio primeiramente para testar. Funcionaria pra qualquer caso onde o a estivesse no meio, como por exemplo:

u jjj k hj a r g b t

Mas, pela resposta ser a G, acho que o exame não quer que analisemos dessa maneira...

GUJ Hacker Membro desde: 26/09/2009 09:18:56 Mensagens: 5750 Offline

Ah, é que o exame não está preocupado com o funcionamento interno de binarySearch e que tenha calhado que, para aquele conjunto de dados em particular, ele conseguisse encontrar a resposta certa, mesmo violando a condição de funcionamento.
A ideia é que você saiba que binarySearch requer uma sequência ordenada - até porque os detalhes de implementação de um determinado algoritmo pode mudar de uma versão para outra.
Só para ter uma ideia: o algoritmo de ordenação (Collections.sort, Arrays.sort) será modificado na versão 7 do Java, mas propositadamente isso não é mencionado explicitamente no javadoc, até para você evitar depender disso para que seus programas funcionem corretamente.

JavaTeenager Membro desde: 09/02/2008 01:12:58 Mensagens: 189 Offline

Humm legal. Entendi. Obrigado entanglement

GUJ Master Membro desde: 30/07/2006 16:09:55 Mensagens: 1311 Offline

entanglement wrote:Ah, é que o exame não está preocupado com o funcionamento interno de binarySearch e que tenha calhado que, para aquele conjunto de dados em particular, ele conseguisse encontrar a resposta certa, mesmo violando a condição de funcionamento.
A ideia é que você saiba que binarySearch requer uma sequência ordenada - até porque os detalhes de implementação de um determinado algoritmo pode mudar de uma versão para outra.
Só para ter uma ideia: o algoritmo de ordenação (Collections.sort, Arrays.sort) será modificado na versão 7 do Java, mas propositadamente isso não é mencionado explicitamente no javadoc, até para você evitar depender disso para que seus programas funcionem corretamente.

Olá!

Interessante essa informação, você tem um link dizendo com mais detalhes sobre essa mudança do algoritmo de sort no Java 7? Fiquei curioso!

[]s

Moderador Membro desde: 29/07/2004 16:10:13 Mensagens: 17543 Offline

A partir do build 70 (se não me engano) isso foi implementado. (Agora está no build 83).

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6804124 - "Replace "modified mergesort" in java.util.Arrays.sort with timsort"-

GUJ Master Membro desde: 30/07/2006 16:09:55 Mensagens: 1311 Offline

thingol wrote:A partir do build 70 (se não me engano) isso foi implementado. (Agora está no build 83).

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6804124 - "Replace "modified mergesort" in java.util.Arrays.sort with timsort"-

Show! Muito obrigado!

Notícias, artigos e o maior fórum brasileiro sobre Java