Hilfe bei Binärsuchaufgabe

[kurtisblow]

Hallo,
ich soll ein vorgegebenes Interface implementieren, nur habe ich schon einige Probleme mit der ersten Methode:

	/**
	 * 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() / 2);
		
		if ( haystack.get(mid) == needle )
		{
			find((ArrayList<Unit<Key, Value>>) haystack.subList(0, mid-1), needle);
		}
		
		else if ()
		{
			return find((ArrayList<Unit<Key, Value>>) haystack.subList(mid, haystack.size()), needle);
		}
		
		else return haystack.;
	}

Das Problem besteht darin, das ich nicht weiss, wie ich ein Element von haystack mit dem key needle vergleichen kann?
Ich habe versucht mit ((haystack.get(mid)).equals(needle)) usw, doch ich finde einfach nichts zum vergleichen. Und was soll das für ein Rückgabewert sein? ich will am Schluss ja das object in
haystack, das den gleichen key hat wie needle zurückgeben? also doch return haystack.get(mid) oder?

Kann mir jemand helfen?

mfg Kurt

Edit: sollte wohl ( (needle.compareTo(haystack.get(mid).key)) < 0) sein zum vergleichen oder?

 

[kurtisblow]

Habe jetzt mal das hier:

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

		int mid = (haystack.size() / 2);
		
		if ( (needle.compareTo(haystack.get(mid).key)) < 0)
		{
			find((ArrayList<Unit<Key, Value>>) haystack.subList(mid-1,haystack.size()), needle);
		}
		
		else if ((needle.compareTo(haystack.get(mid).key)) > 0)
		{
			return find((ArrayList<Unit<Key, Value>>) haystack.subList(0, mid+1), needle);
		}
		
		else return haystack.get(mid).value;
	}

geht aber leider immer noch nicht, was muss ich da am Schluss returnen?

 

[kurtisblow]

Ich begreiffe folgendes nicht mehr:

	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;
			
		return null;
	
	}

wenn ich return null; am Schluss der methode nicht habe, gilt die Methode als falsch (erwartet einen Rückgabewert vom Typ Value), doch mit return null erfüllt es nicht alles Junit Tests.
Ich habe im debugger alles durchgegangen, es würde den erwarteten Wert returnen, jedoch kommt ganz am Schluss noch return null und weg ist der erwartete Wert. Was kann ich da machen?

 

[Landei]

Ohne mir jetzt die Logik angeschaut zu haben: Es sieht so aus, als ob in Zeile 14 ein return fehlt.

 

[kurtisblow]

Danke, jetzt klappts beinahe, ich habe das einfach nicht gesehen, egal wie oft ich durch geschauft habe lol.

 

[kurtisblow]

Ich habe nun diesen Test hier, der einfach nicht erfüllt wird.
Im debugger habe ich herausegefunden, das nach dem ersten Durchgang in der zweiten Forschleife (als wenn i = 2) ein haystack der grösse null übergeben wird und somit eine exception geworfen wird.
Ich verändere ja den haystack in meiner Methode, wie kann ich aber machen, das der haystack immer wieder wie am Anfang ist, nach einem String result = search.find(haystack, i); aufruf?

@Test public void generic() 
	{
		ArrayList<Unit<Integer, String>> haystack = new ArrayList<Unit<Integer, String>>();
		int count = 100;
		for (int i=0; i<count; i++) {
			if (i %3 == 0) continue;
			haystack.add(new Unit<Integer, String>(i, String.valueOf(i)));
		}
		
		for (int i=0; i<count; i++) {
			if (i%3 == 0) continue;
			String result = search.find(haystack, i);
			Assert.assertEquals(String.valueOf(i), result);
		}
		
		for (int i=0; i<=count; i++) {
			if (i%3 == 0) {
				String result = search.find(haystack, i);
				Assert.assertEquals(null, result);
			}
		}
	}

Hier noch meine fertige methode:

	public Value find(ArrayList<Unit<Key, Value>> haystack, Key needle)
	{
		int mid = (haystack.size() / finalFactor) ;
		
		if ( haystack.isEmpty())
		{
			return null;
		}
		
		else if ((needle.compareTo(haystack.get(mid).key)) == 0)
		{
			return haystack.get(mid).value;
		}

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

 

[kurtisblow]

Ich habe jetzt einmal folgendes evrsucht:

	ArrayList <Unit<Key, Value>> list = null;
	
	/**
	 * 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)
	{
		list.clear();
		int mid = (haystack.size() / finalFactor) ;
		
		if  (haystack.isEmpty())
			return null;
		
		
		else if ((needle.compareTo(haystack.get(mid).key)) == 0)
			return haystack.get(mid).value;
	

		else if ( (needle.compareTo(haystack.get(mid).key)) < 0)
		{
			//haystack.subList(mid, haystack.size()).clear();
			for (int i = 0; i<haystack.size();i++)
				list.add(haystack.get(i));
			list.subList(mid, haystack.size()).clear();
			return find(list, needle); 
		}
		
		else if ((needle.compareTo(haystack.get(mid).key)) > 0)
		{
			//haystack.subList(0, mid).clear();
			for (int i = 0; i<haystack.size();i++)
				list.add(haystack.get(i));
			list.subList(0, mid).clear();
			return find(list, needle);
			
		}
		
		else return null;
			
	}

funktioniert aber nicht.
Wie genau kann ich einer anderen ArrayList eine subList von haystack hinzufügen?

 

[Landei]

Warum hantierst du mit Unterlisten statt mit Indizes?

    public Value find(ArrayList<Unit<Key, Value>> haystack, Key needle) {
        return helper(haystack, needle, -1, haystack.size());
    }

    private Value helper(ArrayList<Unit<Key, Value>> haystack, Key needle, int from, int to) {
        if (from + 1 == to) return null;
        int mid = (from + to) / 2;
        int cmp = haystack.get(mid).key.compareTo(needle);
        if (cmp < 0) return helper(haystack, needle, mid, to);
        else if (cmp > 0) return helper(haystack, needle, from, mid);
        else return haystack.get(mid).value;
    }

Die -1 wundert mich selbst, aber anders wollte es nicht, und ich war zu faul, es jetzt ganz genau nachzuvollziehen.