Skip to content

Instantly share code, notes, and snippets.

@timlesallen
Last active October 8, 2020 00:34
Show Gist options
  • Save timlesallen/9a74afda15298a5f63c9dfeeba9bd276 to your computer and use it in GitHub Desktop.
Save timlesallen/9a74afda15298a5f63c9dfeeba9bd276 to your computer and use it in GitHub Desktop.
const findMin = array =>
array.find(
(item, index) => item < array[index > 0 ? index - 1 : array.length - 1]
);
const findMinBinarySearch = (array, left = 0, right) => {
if (right === undefined) right = array.length - 1;
if (right - left === 0) return array[left];
const midpoint = Math.floor(left + (right - left) / 2);
// If the right most value of the LHS partition is less than the right most value in the RHS partition, then
// we know that we need to search the LHS because we must have pivoted in the
// LHS. (This could not be true otherwise.)
// And vice versa.
if (array[midpoint] < array[right]) {
return findMinBinarySearch(array, left, midpoint);
}
return findMinBinarySearch(array, midpoint + 1, right);
};
console.log(findMin([7, 9, 0, 2, 4])); // 0
console.log(findMin([0, 2, 4, 7, 9])); // 0
console.log(findMin([2, 4, 7, 9, 0])); // 0
console.log(findMinBinarySearch([7, 9, 0, 2, 4])); // 0
console.log(findMinBinarySearch([0, 2, 4, 7, 9])); // 0
console.log(findMinBinarySearch([2, 4, 7, 9, 0])); // 0
console.log(findMinBinarySearch([2])); // 2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment