Learn/JavaScript/12. Sorting and searching
Lesson 12 of 15
Sign in

JavaScript, lesson 12

Sorting and searching

Putting data in order and finding things in it are two of the most common jobs a program does. JavaScript gives you a powerful built-in sort, but it has a famous trap you need to know first.

The default sort compares text

Without arguments, sort() converts every element to a string and compares the strings character by character, so "100" comes before "9". That is fine for plain words but wrong for numbers.

Compare functions

Pass a compare function (a, b) => ... that returns:

  • a negative number if a should come first,
  • a positive number if b should come first,

2 exercises to try what you just read.

Exercise 1

Leaderboard

Press Ctrl Enter or Check to test your code.

Exercise 2

Find the page

Press Ctrl Enter or Check to test your code.

  • 0 if they are equal for sorting purposes.
  • For strings, use localeCompare, which returns the negative/zero/positive value for you and handles accents properly:

    Two more facts matter:

    • sort changes the array in place and returns the same array. If you need to keep the original, use toSorted(compareFn), which returns a sorted copy.
    • The sort is stable: elements that compare as equal keep their original relative order.

    Sorting by several keys

    Sort objects by one property, and break ties with another, by trying the keys in order:

    The || works because a difference of 0 is falsy: when points tie, the name comparison decides.

    Searching

    For a simple search through any array, use the built-in methods:

    MethodReturns
    includes(x)true or false
    indexOf(x)first index of x, or -1
    find(fn)first element where fn returns true, or undefined
    findIndex(fn)index of that element, or -1
    findLast(fn)the last matching element

    These check elements one by one, so their time grows with the length of the array.

    Binary search

    If the array is sorted, you can do much better. Look at the middle element: if it is too small, the target can only be in the right half; if too big, only in the left half. Each step throws away half of what is left, so a million elements need only about 20 steps.

    JavaScript has no built-in binary search for arrays, so this small function is worth knowing by heart. The tricky parts are the <= in the loop condition and moving lo and hi past mid, never onto it, so the range always shrinks.

    Further reading

    • MDN: Array.prototype.sort
    • MDN: Array.prototype.toSorted
    • MDN: String.prototype.localeCompare
    • MDN: Array.prototype.find

    Each input line is a player and a score: NAME SCORE. Print the leaderboard sorted by score from highest to lowest; players with the same score are listed in alphabetical order of name. Each output line is RANK. NAME SCORE, where rank is the position in the sorted list starting at 1. Names are single words of lower-case letters.

    Sample input:

    Sample output:

    A book's index lists the page numbers where a word appears, in increasing order. The first input line holds those page numbers separated by spaces. Every following line is a page number to look up. For each lookup print page P: position I where I is the zero-based index of P in the list, or page P: not found.

    Write your own binarySearch function; do not use indexOf or includes.

    Sample input:

    Sample output:

    const nums = [10, 9, 1, 100];
    nums.sort();
    console.log(nums);   // [ 1, 10, 100, 9 ]
    nums.sort((a, b) => a - b);   // ascending: [1, 9, 10, 100]
    nums.sort((a, b) => b - a);   // descending: [100, 10, 9, 1]
    const names = ["émile", "Zoe", "adam"];
    names.sort((a, b) => a.localeCompare(b));   // [ 'adam', 'émile', 'Zoe' ]
    const players = [
      { name: "Kim", points: 30 },
      { name: "Ali", points: 45 },
      { name: "Bo", points: 30 },
    ];
    
    players.sort((a, b) => b.points - a.points || a.name.localeCompare(b.name));
    // Ali 45, Bo 30, Kim 30
    const first = players.find((p) => p.points < 40);   // { name: "Kim", points: 30 }
    function binarySearch(sorted, target) {
      let lo = 0;
      let hi = sorted.length - 1;
      while (lo <= hi) {
        const mid = Math.floor((lo + hi) / 2);
        if (sorted[mid] === target) return mid;
        if (sorted[mid] < target) lo = mid + 1;
        else hi = mid - 1;
      }
      return -1;   // not found
    }
    kim 30
    ali 45
    bo 30
    1. ali 45
    2. bo 30
    3. kim 30
    3 8 15 42 99
    42
    4
    page 42: position 3
    page 4: not found