DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’» is a community of 966,904 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
Cover image for Natural Search Algorithm
Grzegorz Kućmierz
Grzegorz Kućmierz

Posted on

Natural Search Algorithm

This post is about function I wrote while solving LeetCode task.

Complexity of naive solution for this task is O(wΒ²) where w is weights size.
But it can be done better with little improvement.
Instead checking every possible day from 1 to weights.length we can implement natural search algorithm and finish this task with O(w * log(w)) complexity.

Here is code I wrote:
https://github.com/gkucmierz/algorithms/blob/master/js/natural_search.js

Using this function is very simple.
Whenever we have Signum function with unknown bias.

Alt Text

Like this:

const fn = n => Math.sign(n - 345) >= 0;

345 here is random unknown number.
We can easily find it using simple code:

const fn = n => Math.sign(n - 345) >= 0;

console.log(naturalSearch(fn));

Second parameter for naturalSearch function which is retFirstTrue indicates if function should return first natural number when condition is returning true value, or last natural number when it is still false.

Lets check if algorithm really is calling function optimal number of times:

const fn = n => {
  const res = n >= 345;
  console.log('checking number:', n, 'result:', res);
  return res;
};

console.log(naturalSearch(fn));

Than we have this result:

'checking number:', 1, 'result:', false
'checking number:', 2, 'result:', false
'checking number:', 4, 'result:', false
'checking number:', 8, 'result:', false
'checking number:', 16, 'result:', false
'checking number:', 32, 'result:', false
'checking number:', 64, 'result:', false
'checking number:', 128, 'result:', false
'checking number:', 256, 'result:', false
'checking number:', 512, 'result:', true
'checking number:', 384, 'result:', true
'checking number:', 320, 'result:', false
'checking number:', 352, 'result:', true
'checking number:', 336, 'result:', false
'checking number:', 344, 'result:', false
'checking number:', 348, 'result:', true
'checking number:', 346, 'result:', true
'checking number:', 345, 'result:', true
345

As we can see in first phase algorithm is trying to find true value by multiplying number by 2, then when it find, it can find exact point using bisection technique.

Top comments (0)

Update Your DEV Experience Level:

Settings

Go to your customization settings to nudge your home feed to show content more relevant to your developer experience level. πŸ›