Probleme bei Binärsuche java

[Kurt T. (kurtisblow)]

Hallo,
ich versuche folgende methode zu implementieren:
Dokumentation dazu:
  private int finalFactor = 2;
  private int countSteps = 0;
  /**
   * Performs a binary search on the vector of {@link Unit}s.
   *
   * @param needle
   *            We are looking for something whose key equals this 
needle with
   *            respect to the {@link Comparable} interface.
   * @param haystack
   *            The vector of {@link Unit}s where we are searching for 
the
   *            needle. This vector must be sorted ascending with 
respect to
   *            the keys and the {@link Comparable} interface.
   * @return A thing from the haystack whose key equals the needle or 
null
   *         if no such thing is in the haystack.
   */

  public Value find(ArrayList<Unit<Key, Value>> haystack, Key needle)
  {

    int mid = (haystack.size() / finalFactor) ;
    
    if ( haystack.isEmpty())
    {
      return null;
    }

    if ( (needle.compareTo(haystack.get(mid).key)) < 0)
    {
      haystack.subList(mid, haystack.size()).clear();
      find(haystack, needle); 
    }
    
    else if ((needle.compareTo(haystack.get(mid).key)) > 0)
    {
      haystack.subList(0, mid).clear();
      return find(haystack, needle);
    }
    
    else return haystack.get(mid).value;
    
                             
    
  }

Ich denke es stimmt alles, doch es gibt ein Problem, nämlich das
die Methode als falsch gilt, wenn ich unten nicht noch ein return null
einfüge, aber dann erfüllt es mir nicht mehr die vorgegebenen JUnit Tests.

[Jasch (Gast)]

Hans Lüthi schrieb:
> Hallo,
> ich versuche folgende methode zu implementieren:
> Dokumentation dazu:
>   private int finalFactor = 2;
>   private int countSteps = 0;

Uhhhh, wird nirgendwo benutzt?

>   /**
>    * Performs a binary search on the vector of {@link Unit}s.

Das ist nicht korrekt. Die Funktion zerstört den übergebenen Vektor ganz 
nebenbei auch noch...

>    *
>    * @param needle
>    *            We are looking for something whose key equals this
> needle with
>    *            respect to the {@link Comparable} interface.
>    * @param haystack
>    *            The vector of {@link Unit}s where we are searching for
> the
>    *            needle. This vector must be sorted ascending with
> respect to
>    *            the keys and the {@link Comparable} interface.
>    * @return A thing from the haystack whose key equals the needle or
> null
>    *         if no such thing is in the haystack.
>    */
>
>
> [code]
>
>
>   public Value find(ArrayList<Unit<Key, Value>> haystack, Key needle)
>   {
>
>     int mid = (haystack.size() / finalFactor) ;

Hmm, und wenn finalFactor jemals != 2 ist passiert was genau? Wozu ist 
finalFactor eine definierte Konstante?

Lass die Klammern aussenrum weg, die sind Unfug.

>     if ( haystack.isEmpty())
>     {
>       return null;
>     }
>
>     if ( (needle.compareTo(haystack.get(mid).key)) < 0)

Überflüssige Klammern weglassen, verwirrt bloss.

>     {
>       haystack.subList(mid, haystack.size()).clear();

Vektor zerstören, warum? Du solltest die (andere!) subList rekursiv an 
find() weitergeben.

>       find(haystack, needle);

Fehlt da nicht ein "return"?

>     }
>
>     else if ((needle.compareTo(haystack.get(mid).key)) > 0)

Klammern.

>     {
>       haystack.subList(0, mid).clear();

Zerstörung.

>       return find(haystack, needle);
>     }
>
>     else return haystack.get(mid).value;
>
>
>
>   }
>
> Ich denke es stimmt alles, doch es gibt ein Problem, nämlich das
> die Methode als falsch gilt, wenn ich unten nicht noch ein return null
> einfüge, aber dann erfüllt es mir nicht mehr die vorgegebenen JUnit
> Tests.

Na ich glaube nicht dass der Compiler so schlau ist dass er unbedingt 
erkennt dass damit alle Möglichkeiten erschöpft sind.

Und es fehlt ein return, damit geben ja nicht alle Zweige etwas zurück.

[Kurt T. (kurtisblow)]

ok, stimmt ja.
wie aber kann ich rekursiv eine Sublist weitergeben?
Ich weiss nur wie ich Elemente löschen kann.
Ich möchte ja aber die andere Sublist übergeben, der Befehl Sublist ist
aber zum löschen von einem Intervall in der List oder?
muss ich irgendwie eine neue Liste erstellen und dann die hälfte der 
Elemente kopieren oder wie würdet ihr das machen?

[Hans M. (hansilein)]

script lesen?

[Kurt T. (kurtisblow)]

Steht nichts dazu was man verwenden soll.
Ich muss aber irgendwie diese subList zurückgeben, so geht es aber 
nicht:

return find(haystack.subList(0, mid), needle);

Aber wie dann?

[Jasch (Gast)]

Kurt Tresen schrieb:
> Steht nichts dazu was man verwenden soll.
> Ich muss aber irgendwie diese subList zurückgeben, so geht es aber
> nicht:

Was heisst "geht nicht" genau? (Fieses Grinsen... ;-)

> return find(haystack.subList(0, mid), needle);
>
> Aber wie dann?

Ich würde mal denken, wenn ich so sehe was subList() zurückgibt, müsste 
man find() wohl so deklarieren:

public Value find(List<Unit<Key, Value>> haystack, Key needle) ...

List<> statt ArrayList<>.

Vorsicht, ich habe es nicht dem Compiler vorgeworfen.

Und aus Sicht der Performance ist das eher ziemlicher Mist.

[Läubi .. (laeubi)]

Jasch schrieb:
> Ich würde mal denken, wenn ich so sehe was subList() zurückgibt, müsste
> man find() wohl so deklarieren:

In der Tat, oder einfach ein newArrayList<...>(sublist) ...

Kurt Tresen schrieb:
> doch es gibt ein Problem, nämlich das
> die Methode als falsch gilt, wenn ich unten nicht noch ein
> return null einfüge
Quatsch, der Compiler meckert nur an das nicht in allen (theoretisch 
möglichen) Wegen ein returnvalue steht, z.B. heir soll wohl auch noch 
ein return find(...) hin.

Kurt Tresen schrieb:
> find(haystack, needle);

Kurt Tresen schrieb:
> aber dann erfüllt es mir nicht mehr die vorgegebenen JUnit Tests

Weil dein Code dan fallsch ist, teste (und debugge) den doch einfach mal 
mit ein paar simplen Beispielen!

Kurt Tresen schrieb:
> Ich möchte ja aber die andere Sublist übergeben, der Befehl Sublist ist
> aber zum löschen von einem Intervall in der List oder?

Doku lesen, da steht nix davon, dass das für das löschen zuständig wäre!
Das löschen ist auch komplett unötig hier!