80

I want to use the binary search algorithm to search the string which has been entered by the user in a very big sorted file. I can not compare the string which has been entered by the user with the string which has been located in the middle line of the file to continue my binary search.

For example, if the user's string is abcda and the file's string is abcza, it is obvious that the user's string is smaller than the file's string. How is it implemented in java? it will be great if you can help me with a sample code.

sylvester
  • 887
  • 1
  • 10
  • 18
  • 3
    You should specify if you need this to work only with English (ASCII) strings, or if the input can potentially be international. Determining which string sorts before another is quite complex, in the latter case. – unwind Mar 01 '11 at 11:02

4 Answers4

149

You can use

str1.compareTo(str2);

If str1 is lexicographically less than str2, a negative number will be returned, 0 if equal or a positive number if str1 is greater.

E.g., 

"a".compareTo("b"); // returns a negative number, here -1
"a".compareTo("a"); // returns  0
"b".compareTo("a"); // returns a positive number, here 1
"b".compareTo(null); // throws java.lang.NullPointerException
Jacob van Lingen
  • 8,989
  • 7
  • 48
  • 78
Johan Sjöberg
  • 47,929
  • 21
  • 130
  • 148
  • 15
    No. The contract of java.util.Comparable says that it will return a negative integer if the first one is lesser than the second one, and a positive integer if greater. But not necessarily -1 and 1. – JB Nizet Mar 01 '11 at 11:03
  • Thanks. But if the first string is " abc" and the second string is "abc". How can I compare "<" with "a"? – sylvester Mar 01 '11 at 11:06
  • 2
    @sylvester, that's a completely different problem. You need to sanitize your strings before comparison using your favourite method. – Johan Sjöberg Mar 01 '11 at 11:08
  • 2
    @sylvester: The compareTo method of String simply compares the unicode values of the individual characters, thus `'<'` (= 60) is smaller than `'a'` (= 97). As said, if you want to sort both as `abc`, you'll have to strip off the tags and spaces. And you probably want to use a Collator for your language on the result. – Paŭlo Ebermann Mar 01 '11 at 19:06
6

If you would like to ignore case you could use the following:

String s = "yip";
String best = "yodel";
int compare = s.compareToIgnoreCase(best);
if(compare < 0){
    //-1, --> s is less than best. ( s comes alphabetically first)
}
else if(compare > 0 ){
// best comes alphabetically first.
}
else{
    // strings are equal.
}
Alex Spencer
  • 834
  • 2
  • 12
  • 23
3

Haven't you heard about the Comparable interface being implemented by String ? If no, try to use

"abcda".compareTo("abcza")

And it will output a good root for a solution to your problem.

Riduidel
  • 22,052
  • 14
  • 85
  • 185
-1
String bigString = null;

        for(int i = 0; i < number; i++){
            System.out.println("... ");
            String sentence = sc.nextLine();
            if(bigString == null || sentence.compareTo(bigString) > 0) {
                bigString = sentence;
            }
        }
        System.out.println("...: " + bigString);
Harshad Pansuriya
  • 20,189
  • 8
  • 67
  • 95
Programmer
  • 1