Binær søgning

burde måske lige tilføje at jeg udemærket er klar over jeg skal ændre på mit søge interval når jeg finder strengen, jeg kan bare ikke lige gennemskue hvad jeg skal ændre den til

Jeg ville nok lade den første while løkke kun finde et mid der matcher og
så lave to nye while løkker:
  - en der går baglæns og finder den første som matcher
  - en anden som går forlæns og tilføjer til Vector så længde de matcher

jeg har nørklet lidt med det, og kom frem til følgende, problemet er blot den berømte "Off By One", jeg ved med sikkerhed strengen findes 3 gange i min vector, men allligevel indeholder min nye vector kun 2 objecter, nogen hints ? :-)

og lidt kode:

    public static Vector findProdukt(Vector produkter, String søgenavn) {
        Vector p = new Vector();
        boolean found = false;
        String s = null;
        int left = 0;
        int right = produkter.size() - 1;
        int mid = 0;
        while (!found && (left <= right)) {
            mid = (left + right) / 2;
            s = ((Produkt) produkter.get(mid)).getNavn();
            if (søgenavn.compareTo(s) > 0) {
                left = mid + 1;
            } else if (søgenavn.compareTo(s) < 0) {
                right = mid - 1;
            } else if (søgenavn.equals(s)) {
                System.out.println("fundet");
                p.add(produkter.get(mid));
                found = true;
            }
        }
        left = mid - 1;
        right = mid + 1;
        while (søgenavn.equals(((Produkt) produkter.get(left)).getNavn())
                && (left >= 0)) {
            p.add(produkter.get(left));
            left--;
        }
        while (søgenavn.equals(((Produkt) produkter.get(right)).getNavn())
                && (right < produkter.size() - 1)) {
            p.add(produkter.get(right));
            right++;
        }
        return p;
    }

(right <= produkter.size() - 1)

eller

(right < produkter.size())

måske

er afprøvet, og giver mig en indexoutofbounds på min vector

Ovenstående kombineret med at du tester for left og rigth inden di tester for værdi ?

while ((left >= 0) && søgenavn.equals(((Produkt) produkter.get(left)).getNavn())) {
            p.add(produkter.get(left));
            left--;
        }
        while ((right < produkter.size()) && søgenavn.equals(((Produkt) produkter.get(right)).getNavn()))) {
            p.add(produkter.get(right));
            right++;
        }

right < (produkter.size() <-- giver indexoutofbounds
right < (produkter.size() -1 <-- mangler et element

Har du også prøve at ændre rækkefølgen som vist ovenfor ?

ahh nej, og det hjalp en hel del, jeg takker ærbødigt, kan entlig godt se logikken i at tjekke om indexet er løbet udover den tilladte størrelse før man forsøger at kalde et element, smider du lige et svar ? :)

svar

Nogle sprog heriblandt Java shortcutter AND d.v.s. at først evalueres
første udtryk og kun hvis det er sandt evalueres andet udtryk.

Andre sprog evaluerer altid alle udtryk.

ikke lige det man lærer når man har om logiske kvantore på uni. owell så lærte jeg også noget i dag :-)