Search

[Gilgamesh]

I have a string vector having strings in an alphabetical order. I use contains() to check if it contains specific strings. Obviously this search is linear, how can I convert it into string binary search?

[hardwired]

how can I convert it into string binary search
You can write a contains or search method in the class that is working with the Vector, or subclass Vector and: add a method to do binary search or override the contains method or do both, calling the binary search method from contains. You can set it up any way you like when doing this.

Code:

class Pseudo {
    Vector vector;

    /** instance method */
    String contains(String target) {
        // do binary search for target in vector
    }
}
class MyVector extends Vector {
    /** override contains method */
    public boolean contains(Object elem) {
        // do your binary search here
        // or call a local method below
        //    to do the binary search
    }

    /** with or without overriding contains */
    private_or_public boolean binaryContains(Type arg) {
        // binary search for arg
    }
}

[Gilgamesh]

int binarySearch (String word, Vector <String> AlphabetizedListVector){
int lefthand=0;
int righthand=AlphabetizedListVector.size() - 1;
while (lefthand <= righthand){
int mid =( lefthand + righthand ) / 2;
int cmp = word.compareToIgnoreCase(AlphabetizedListVector.ge t(mid));
if (cmp == 0) return mid;
if (cmp < 0){
righthand = mid-1;
}else{
lefthand = mid+1;
}
}
return -1;
// System.out.println("The word "+word+" does not exist.");
}

a) am i making a mistake on this?

Code:

(String word, Vector <String> AlphabetizedListVector)

? it says syntax errors on tokens regarding the parentheses and the comma, ';' expected.

b) how can I instead of 'return -1', print out that the word does not appear in the Vector? thanx

[hardwired]

I tried your code and, after fixing the typo ("ge t") it works okay. The compile errors must be from something else. The error usually gives the line number.

Code:

    public static void main(String[] args) {
        String s = "hello world we are here";
        String[] strs = s.split("\\s");
        Vector<String> v = new Vector<String>();
        for(int j = 0; j < strs.length; j++) {
            v.add(strs[j]);
        }
        int n = binarySearch("we", v);
        System.out.println("n = " + n);
    }

    static int binarySearch (String word, Vector <String> AlphabetizedListVector){ 
        int lefthand=0;
        int righthand=AlphabetizedListVector.size() - 1;
        while (lefthand <= righthand){
            int mid =( lefthand + righthand ) / 2;
            int cmp = word.compareToIgnoreCase(AlphabetizedListVector.get(mid));
            if (cmp == 0) return mid;
            if (cmp < 0){
                righthand = mid-1;
            }else{
                lefthand = mid+1;
            }
        }
        return -1; 
//        System.out.println("The word "+word+" does not exist.");
    }

[Gilgamesh]

a) im sending you the pic to understand me better

b) how (and where exactly in the .java) can I printout ("The word "+word+" does not exist.") when the word is not found in the Vector?

1000 thanks

[hardwired]

im sending you the pic to understand me better
I have no idea what that means, must be some ide thing. Try commenting the entire method out and commenting out the calls to it and see where it takes you.
where can I printout "The word "+word+" does not exist." when the word is not found in the Vector

Code:

        }
        System.out.println("The word "+word+" does not exist.");
        return -1; 
    }