1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
function findRotationPoint(xs: Array<string>): number {
// Find the rotation point in the vector.
let beg = 0;
let end = xs.length - 1;
while (beg != end) {
let mid = beg + Math.floor((end - beg) / 2);
if (beg === mid) {
return xs[beg] < xs[end] ? beg : end;
}
if (xs[end] <= xs[mid]) {
beg = mid;
end = end;
} else {
beg = beg;
end = mid;
}
}
return beg;
}
// Tests
let desc;
let actual;
let expected;
desc = "small array one";
actual = findRotationPoint(["cape", "cake"]);
expected = 1;
assertEquals(actual, expected, desc);
desc = "small array two";
actual = findRotationPoint(["cake", "cape"]);
expected = 0;
assertEquals(actual, expected, desc);
desc = "medium array";
actual = findRotationPoint(["grape", "orange", "plum", "radish", "apple"]);
expected = 4;
assertEquals(actual, expected, desc);
desc = "large array";
actual = findRotationPoint([
"ptolemaic",
"retrograde",
"supplant",
"undulate",
"xenoepist",
"asymptote",
"babka",
"banoffee",
"engender",
"karpatka",
"othellolagkage"
]);
expected = 5;
assertEquals(actual, expected, desc);
function assertEquals(a, b, desc) {
if (a === b) {
console.log(`${desc} ... PASS`);
} else {
console.log(`${desc} ... FAIL: ${a} != ${b}`);
}
}
|
