Skip to content

Instantly share code, notes, and snippets.

@Sauloxd
Created November 27, 2017 02:58
Show Gist options
  • Save Sauloxd/09c190d3f3c280b1351fc0b14d1c77b9 to your computer and use it in GitHub Desktop.
Save Sauloxd/09c190d3f3c280b1351fc0b14d1c77b9 to your computer and use it in GitHub Desktop.
Find how many in a given array A are larger than a given K, without exploding node engine
function findLargerInAofK(A_array, K_array) {
const A = A_array.sort((a, b) => a - b)
return K_array.map(K => {
let supportArrayIndex = [0, A.length - 1]
while (true) {
let middleIndex = Math.ceil((supportArrayIndex[1] + supportArrayIndex[0]) / 2)
if (K >= A[A.length - 1]) return 0
if (K < A[0]) return A.length
if (A[middleIndex] < K) {
supportArrayIndex = [middleIndex, supportArrayIndex[1]]
}
if (A[middleIndex] === K) {
let hasFound = false;
while (!hasFound) {
if (A[middleIndex + 1] === K) {
middleIndex += 1
} else {
K === 3 && console.log(middleIndex)
return A.length - (middleIndex + 1)
}
}
}
if (A[middleIndex] > K) {
if (A[middleIndex - 1] <= K) {
return A.length - middleIndex
}
supportArrayIndex = [0, middleIndex]
}
}
})
}
const size = 1E5
const A = Array(size).fill(0).map(() => Math.floor(Math.random() * 10E9))
const K = Array(size).fill(0).map(() => Math.floor(Math.random() * 10E9))
console.log(new Date())
console.log(findLargerInAofK(A, K))
console.log(new Date())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment