514

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?

sg7
  • 6,108
  • 2
  • 32
  • 40
HRJ
  • 17,079
  • 11
  • 56
  • 80
  • 13
    `return str1 < str2 ? -1 : str1 > str2;`? – 1'' Jul 20 '13 at 18:13
  • 4
    @1" That's not optimal; requires two string comparisons. – HRJ Jul 21 '13 at 08:53
  • 3
    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. – 1'' Jul 21 '13 at 16:20
  • @1" You are right! I ran a largish benchmark and noticed a big lag with `localeCompare`. This is what MDN says about `localeCompare`: "When comparing large numbers of strings, such as in sorting large arrays, it is better to create an Intl.Collator object and use the function provided by its compare property." Unfortunately it is not implemented in Firefox yet! – HRJ Jul 22 '13 at 05:52
  • 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. – Pizzaiola Gorgonzola May 04 '14 at 07:10
  • 2
    I recommend reopening this question, rather than referring to a question about `strcmp` even though the answer to that question is the same, because I think that not all people searching for an answer to this question will know about `strcmp`. – Dan Nissenbaum Nov 26 '15 at 07:16
  • I needed it to return an integer. `return +(str1 < str2 ? -1 : str1 > str2);` – BlindWanderer Feb 26 '16 at 03:14
  • 1
    @HRJ it's not possible to resolve to three possible outcomes (-1,0,1) without two comparisons. – dzimney Feb 06 '21 at 20:11
  • This question asks for the optimal way to compare strings, but is marked as a duplicate of a function that simply compares strings, without mentioning anything about the optimal means. – Lee Goddard Jan 23 '23 at 08:51
  • Poorly asked question and much more frustrating cheerleaders commenting on the answers. To compare strings, more than one comparison is necessary, period. Here, I believe is a function that best fulfills what the original question asks and is slightly (10%) faster than the ternary option in my testing. Have fun! ```function strcmp( a, b ) { for( let i=0 ; i>31 ) || 1 ); } const n = a.length - b.length; return n && ( ( n>>31 ) || 1 ); }``` – NastyCarl Mar 17 '23 at 00:38

3 Answers3

689

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:

Lee Goddard
  • 10,680
  • 4
  • 46
  • 63
Daniel Vassallo
  • 337,827
  • 72
  • 505
  • 443
  • 14
    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. – kennebec Jan 30 '10 at 18:32
  • 32
    You can use toLowerCase or toLocaleLowerCase when you want case insensitive comparisons. – Fabrice Mar 03 '11 at 11:18
  • 2
    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. – JoshVarty Mar 21 '12 at 03:36
  • `''.localeCompare.call(string_a, string_b);` – Ilya Kharlamov May 07 '13 at 09:53
  • I don't understand the > and < when comparing strings... – PositiveGuy May 30 '13 at 14:34
  • 10
    Apparently you're better off comparing it yourself; http://jsperf.com/localecompare – Gerben Jacobs Jul 12 '13 at 13:36
  • 2
    @GerbenJacobs Thanks for that. I also derived a bigger benchmark (binary search) out of that: http://jsperf.com/localecompare/2 – HRJ Jul 22 '13 at 05:53
  • 1
    jsperf.com/localecompare is wrong, there is invalid expression: s1 < **s1** ? -1 : s1 > s2 ? 1 : 0; – vf. Feb 26 '14 at 14:33
  • What if the values being sorted could be strings OR numbers, and you don't know at design time? `String.prototype.localeCompare.call(a, b)` ? – Alex McMillan Oct 22 '15 at 02:49
  • 1
    Should favor using ```===``` as the first comparison. It's faster than < or >. Wrote a new jsperf revision to demonstrate: http://jsperf.com/localecompare/33 – kayakyakr Jan 27 '16 at 17:25
  • I see that in 2021 localeCompare works good and old comments about result deviation in a different browsers are no longer actual – Yura Nov 17 '21 at 09:23
  • why use localeCompare and not `===` ? https://linuxhint.com/compare-strings-in-javascript/ – Tzachi Elrom Jul 05 '23 at 07:22
82

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));  
}
Cipi
  • 11,055
  • 9
  • 47
  • 60
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;
}
Gumbo
  • 643,351
  • 109
  • 780
  • 844
  • 12
    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 Jan 30 '10 at 16:06
  • 1
    @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.) – Gumbo Jan 30 '10 at 16:49
  • 2
    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 Jan 30 '10 at 17:06
  • @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 Jan 30 '10 at 17:45
  • @Gumbo localeCompare doesn't have to be in Javascript right? It could be natively implemented. Or I have missed something... – HRJ Jan 31 '10 at 04:01
  • Maybe I'm missing something. When you code up two completely separate Javascript string comparisons, what happens? Well, the first comparison gets started and (let's say) it notices a mismatch at character position 5. That is, characters 1 through 4 match, but character 5 mismatches. If the first Javascript comparison is a "!=" comparison (or "=="; whatever), then we know that the strings are not equal. However, in the low-level comparison code, we also know the answer to "<" and ">". But we throw away that knowledge when we start the next (Javascript) comparison, and re-compare chars 1-4. – Pointy Jan 31 '10 at 16:47
  • @Pointy: You probably meant something like the algorithm in my update, right? – Gumbo Jan 31 '10 at 17:17
  • @Gumbo yes, exactly. Of course, "localeCompare" is part of the runtime and therefore a C/C++ (or whatever) implementation. I wonder how good a job V8 would do at optimizing out the "charAt" calls? – Pointy Feb 01 '10 at 13:47