mirror of
https://github.com/TheAlgorithms/JavaScript.git
synced 2025-07-06 09:28:26 +08:00
820f8e9c29
* Create first_relative_max_point_in_array.js go over randomly generated array and print first spike or maximum point index in it runs in O(log(n)) * rename file to match requested casing * add comments I prefer SOLID standards so that's why didn't add them at first but due to the repository requirements was needed to be added * remove template unrelated comments * Update equals check to match JavaScript standards * create file skafolding and adjust filename to reflect main function * using newer node version * add tests * add last line as empty line * style changes * move algorithm tests to test folder * revert to old package lock file * chore: add ending line feed Co-authored-by: Rak Laptudirm <raklaptudirm@gmail.com>
31 lines
1.3 KiB
JavaScript
31 lines
1.3 KiB
JavaScript
/**
|
|
* [LocalMaxima](https://www.geeksforgeeks.org/find-indices-of-all-local-maxima-and-local-minima-in-an-array/) is an algorithm to find relative bigger numbers compared to their neighbors
|
|
*
|
|
* Notes:
|
|
* - works by using divide and conquer
|
|
* - the function gets the array A with n Real numbersand returns the local max point index (if more than one exists return the first one)
|
|
*
|
|
* @complexity: O(log(n)) (on average )
|
|
* @complexity: O(log(n)) (worst case)
|
|
* @flow
|
|
*/
|
|
const findMaxPointIndex = (array, rangeStartIndex, rangeEndIndex, originalLength) => {
|
|
// find index range middle point
|
|
const middleIndex = rangeStartIndex + parseInt((rangeEndIndex - rangeStartIndex) / 2)
|
|
|
|
// handle array bounds
|
|
if ((middleIndex === 0 || array[middleIndex - 1] <= array[middleIndex]) &&
|
|
(middleIndex === originalLength - 1 || array[middleIndex + 1] <= array[middleIndex])) {
|
|
return middleIndex
|
|
} else if (middleIndex > 0 && array[middleIndex - 1] > array[middleIndex]) {
|
|
return findMaxPointIndex(array, rangeStartIndex, (middleIndex - 1), originalLength)
|
|
} else {
|
|
// regular local max
|
|
return findMaxPointIndex(array, (middleIndex + 1), rangeEndIndex, originalLength)
|
|
}
|
|
}
|
|
|
|
const LocalMaximomPoint = (A) => findMaxPointIndex(A, 0, A.length - 1, A.length)
|
|
|
|
export { LocalMaximomPoint }
|