531

I am trying to optimize a function which does binary search of strings in JavaScript.

Binary search requires you to know whether the key is == the pivot or < the pivot.

But this requires two string comparisons in JavaScript, unlike in C like languages which have the strcmp() function that returns three values (-1, 0, +1) for (less than, equal, greater than).

Is there such a native function in JavaScript, that can return a ternary value so that just one comparison is required in each iteration of the binary search?

Improve this question
8
  • 14
    return str1 < str2 ? -1 : str1 > str2;? Commented Jul 20, 2013 at 18:13
  • 6
    @1" That's not optimal; requires two string comparisons. Commented Jul 21, 2013 at 8:53
  • 4
    It's still an order of magnitude (!) faster than localeCompare() on my machine. @Gumbo's custom strcmp() may be faster, depending on how optimized the internal implementation of equality comparisions for strings is. Commented Jul 21, 2013 at 16:20
  • 4
    you need two compares anyway !, one to see if a > b another to see if they are equal, javascript is VERY fast determining if strings are equal, because, if they are equal they are one and the same object, it's like comparing two pointers, strings are "atomized", stored in a hash table, so of every combination of letters, only one instance exists. Commented May 4, 2014 at 7:10
  • 1
    @HRJ it's not possible to resolve to three possible outcomes (-1,0,1) without two comparisons. Commented Feb 6, 2021 at 20:11

3 Answers 3

Reset to default
704

You can use the localeCompare() method.

string_a.localeCompare(string_b);

/* Expected Returns:

 0:  exact match

-1:  string_a < string_b
 
 1:  string_a > string_b

 */

Further Reading:

Improve this answer
Sign up to request clarification or add additional context in comments.

12 Comments

Unfortunately, stringCompare is not reliable. Opera, IE, Firefox, Chrome and Safari all return 1 for 'dog'.localeCompare('cat'), which is to be expected, and -1 when you reverse the caller and the argument. BUt capital letters behave oddly- 'dog'.localeCompare('Dog') Of the browsers I tested, only Safar 4 returned 1. It returns -1 in IE8 and firefox 3, and Opera 9 and Chrome both return +32.
You can use toLowerCase or toLocaleLowerCase when you want case insensitive comparisons.
I think it's important to note that V8 (Chrome) seems to interpret ECMA-262 differently than IE/Firefox on localeCompare. For example: "a".localeCompare("Z") should return -1 but instead returns 7 which is the charcode of "a" - charcode of "Z". Unfortunately, the language in the specification is loose, specifying that localeCompare() returns negative number, a positive number or 0. (Not specifically -1, 1, 0). I filed a bug report in the hope this might change, but it's been an issue since August 2010, so I doubt it will.
Apparently you're better off comparing it yourself; jsperf.com/localecompare
@GerbenJacobs Thanks for that. I also derived a bigger benchmark (binary search) out of that: jsperf.com/localecompare/2
|
84

Well in JavaScript you can check two strings for values same as integers so yo can do this:

  • "A" < "B"
  • "A" == "B"
  • "A" > "B"

And therefore you can make your own function that checks strings the same way as the strcmp().

So this would be the function that does the same:

function strcmp(a, b)
{   
    return (a<b?-1:(a>b?1:0));  
}
Improve this answer

1 Comment

Again, read the original question!! The point is to avoid doing more than one string comparison.
15

You can use the comparison operators to compare strings. A strcmp function could be defined like this:

function strcmp(a, b) {
    if (a.toString() < b.toString()) return -1;
    if (a.toString() > b.toString()) return 1;
    return 0;
}

Edit    Here’s a string comparison function that takes at most min { length(a), length(b) } comparisons to tell how two strings relate to each other:

function strcmp(a, b) {
    a = a.toString(), b = b.toString();
    for (var i=0,n=Math.max(a.length, b.length); i<n && a.charAt(i) === b.charAt(i); ++i);
    if (i === n) return 0;
    return a.charAt(i) > b.charAt(i) ? -1 : 1;
}
Improve this answer

8 Comments

But this routine does exactly what the OP doesn't want to do: there are two string comparisons (let alone those function calls to "toString").
@Pointy: It’s not possible with just one comparison. You need at least min {a.length, b.length} steps (compare two characters at a time) to determine if the strings are equal or not. (Even localeCompare will do that internally.)
No, localeCompare will not do that internally. Comparing the characters is implemented as a subtraction, so as soon as there's a non-zero result of that operation you know the answer. Your answer can re-compare possibly all the characters of each string.
@Pointy: But the substraction is done character by character. And that’s the point. That takes at most (and not at least as I wrote) min {a.length, b.length} steps (in the case where both strings are equal). But you’re right. It’s better to test for equality first as that takes the most steps.
@Gumbo localeCompare doesn't have to be in Javascript right? It could be natively implemented. Or I have missed something...
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.