CODEWITHSUNDEEP
javascriptlodash
danday74
danday74

Reputation: 56936

JavaScript find first number in array that is <= to given number

I have an array of prime numbers:

const primes = [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

I want to find the first number in this list that is <= the number given.

For example ... getHighestPrimeNumber(58) ... should return 53, being the prime number with the greatest value which is also less than or equal to 58

Expect results:

getHighestPrimeNumber(58) === 53

getHighestPrimeNumber(53) === 53

getHighestPrimeNumber(52) === 47

My current approach is to iterate through the prime numbers but this is very inefficient, especially given that there may be 10,000+ numbers in the list - thanks

Vanilla JS or Lodash is fine

Upvotes: 2

Views: 164

Answers (3)

Akrion
Akrion

Reputation: 18515

Since you posted this with lodash tag just FYI that this with it is trivial due to _.sortedIndex:

const primes = [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

const closestPrime = (n) => {
  let index = _.sortedIndex(primes, n)
  return primes[index] == n ? primes[index] : primes[index-1]
}

console.log(closestPrime(58))
console.log(closestPrime(53))
console.log(closestPrime(52))
<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.10/lodash.min.js"></script>

Upvotes: 4

ggorlen
ggorlen

Reputation: 56865

This is a good task for a binary search:

const bisect = (needle, haystack) => {
  let lo = 0;
  let hi = haystack.length;
  
  while (lo <= hi) {
    const mid = ~~((hi - lo) / 2 + lo);
    
    if (haystack[mid] === needle) {
      return needle;
    }
    else if (haystack[mid] > needle) {
      hi = mid - 1;
    }
    else {
      lo = mid + 1;      
    }
  }
  
  return haystack[hi];
};

const getHighestPrimeNumber = n => {
  const primes = [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97];
  return bisect(n, primes);
};

console.log(getHighestPrimeNumber(58) === 53);
console.log(getHighestPrimeNumber(53) === 53);
console.log(getHighestPrimeNumber(52) === 47);

A couple of notes:

  • You'll likely want to make your prime number array a parameter to getHighestPrimeNumber so it isn't created and garbage collected on every function call. At this point, you might as well just call the binary search directly.
  • If you're concerned about queries over and under the bounds of the array, you can handle those according to some policy, for example: return haystack[Math.min(hi,haystack.length-1)];.
  • Binary search is O(n log(n)) time complexity. Set lookups are O(1), so you may experience a performance boost if you maintain a set in addition to the array and try lookups there first.

Upvotes: 1

Jacek Lipiec
Jacek Lipiec

Reputation: 432

Seems like a field for a divide and conquer approach. Something like a Binary search:

const primes = [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

function findHighestPrimeNumberRecursive(arr, ceiling) {
  const midpoint = arr.length/2
  if(arr[midpoint ] === ceiling){
    // we found it!
    return primes[arr.length-1];
  } else {
    if(arr[midpoint] <== ceiling) {
      return findHighestPrimeNumberRecursive(arr.slice(0, midpoint), ceiling);
    } else {
      return findHighestPrimeNumberRecursive(arr.slice(midpoint, arr.length), ceiling);
    }
  }
}

function getHighestPrimeNumber(ceiling) {
  return findHighestPrimeNumberRecursive(primes, ceiling);
}

Upvotes: 1

Related Questions