JavaScript, lesson 12
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.
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.
Pass a compare function (a, b) => ... that returns:
a should come first,b should come first,2 exercises to try what you just read.
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.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.
For a simple search through any array, use the built-in methods:
| Method | Returns |
|---|---|
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.
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.
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 30const 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 301. ali 45
2. bo 30
3. kim 303 8 15 42 99
42
4page 42: position 3
page 4: not found