Skip to content

Instantly share code, notes, and snippets.

@johannes-weber

johannes-weber/index.html

Created January 15, 2018 23:25
Show Gist options
  • Save johannes-weber/7461c5946be1a6efbcecc00327d97576 to your computer and use it in GitHub Desktop.
Save johannes-weber/7461c5946be1a6efbcecc00327d97576 to your computer and use it in GitHub Desktop.
Download ZIP
JS Bin // source https://jsbin.com/yizase
Raw
index.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width">
<title>JS Bin</title>
</head>
<body>
<script id="jsbin-javascript">
// Source: http://algorithms.tutorialhorizon.com/find-the-local-minima-in-a-given-array/
// runtime complexity: O(log n), space complexity: O(1)
function findLocalMinima(input) {
if (!input || input.length < 1) {
throw new Error('input has to have at least 2 elements');
}
if (input.length == 1) {
return input[0];
}
let floor = 0;
let ceiling = input.length - 1;
while(floor <= ceiling) {
let middle = Math.ceil((ceiling - floor) / 2) + floor;
if (
(!input[middle - 1] && input[middle] < input[middle + 1]) ||
(!input[middle + 1] && input[middle] < input[middle - 1]) ||
(input[middle] < input[middle + 1] && input[middle] < input[middle - 1])
) {
return input[middle];
}
if (input[middle - 1] < input[middle]) {
// go left
ceiling = middle - 1;
} else {
// go right
floor = middle + 1;
}
}
}
console.log('expect: 2', findLocalMinima([11, 4, 2, 5, 11, 13, 5]));
console.log('expect: 3', findLocalMinima([3]));
console.log('expect: 1', findLocalMinima([1, 2, 3, 4]));
</script>
<script id="jsbin-source-javascript" type="text/javascript">// Source: http://algorithms.tutorialhorizon.com/find-the-local-minima-in-a-given-array/
// runtime complexity: O(log n), space complexity: O(1)
function findLocalMinima(input) {
if (!input || input.length < 1) {
throw new Error('input has to have at least 2 elements');
}
if (input.length == 1) {
return input[0];
}
let floor = 0;
let ceiling = input.length - 1;
while(floor <= ceiling) {
let middle = Math.ceil((ceiling - floor) / 2) + floor;
if (
(!input[middle - 1] && input[middle] < input[middle + 1]) ||
(!input[middle + 1] && input[middle] < input[middle - 1]) ||
(input[middle] < input[middle + 1] && input[middle] < input[middle - 1])
) {
return input[middle];
}
if (input[middle - 1] < input[middle]) {
// go left
ceiling = middle - 1;
} else {
// go right
floor = middle + 1;
}
}
}
console.log('expect: 2', findLocalMinima([11, 4, 2, 5, 11, 13, 5]));
console.log('expect: 3', findLocalMinima([3]));
console.log('expect: 1', findLocalMinima([1, 2, 3, 4]));</script></body>
</html>
Raw
jsbin.yizase.js
// Source: http://algorithms.tutorialhorizon.com/find-the-local-minima-in-a-given-array/
// runtime complexity: O(log n), space complexity: O(1)
function findLocalMinima(input) {
if (!input || input.length < 1) {
throw new Error('input has to have at least 2 elements');
}
if (input.length == 1) {
return input[0];
}
let floor = 0;
let ceiling = input.length - 1;
while(floor <= ceiling) {
let middle = Math.ceil((ceiling - floor) / 2) + floor;
if (
(!input[middle - 1] && input[middle] < input[middle + 1]) ||
(!input[middle + 1] && input[middle] < input[middle - 1]) ||
(input[middle] < input[middle + 1] && input[middle] < input[middle - 1])
) {
return input[middle];
}
if (input[middle - 1] < input[middle]) {
// go left
ceiling = middle - 1;
} else {
// go right
floor = middle + 1;
}
}
}
console.log('expect: 2', findLocalMinima([11, 4, 2, 5, 11, 13, 5]));
console.log('expect: 3', findLocalMinima([3]));
console.log('expect: 1', findLocalMinima([1, 2, 3, 4]));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment