current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Join the Stack Overflow Community
Stack Overflow is a community of 6.6 million programmers, just like you, helping each other.
Join them; it only takes a minute:
Sign up
up vote 0 down vote favorite

I have prepared 2 Javascript functions to find matching integer pairs that add up to a sum and returns a boolean.

The first function uses a binary search like that:

function find2PairsBySumLog(arr, sum) {
 for (var i = 0; i < arr.length; i++) {
   for (var x = i + 1; x < arr.length; x++) {
     if (arr[i] + arr[x] == sum) {
       return true;
     }
   }
 }
 return false;
}

For the second function I implemented my own singly LinkedList, in where I add the complementary integer to the sum and search for the value in the LinkedList. If value is found in the LinkedList we know there is a match.

function find2PairsBySumLin(arr, sum) {
  var complementList = new LinkedList();
  for (var i = 0; i < arr.length; i++) {
    if (complementList.find(arr[i])) {
      return true;
    } else {
      complementList.add(sum - arr[i]);
    }
  }
  return false;
}

When I run both functions I clearly see that the second function executes ~75% faster

var arr =  [1,2,4,1,3,2,9,8,1,9,10,1,2,8,9,8,2,4];

console.time('Binary');
console.log(find2PairsBySumLog(arr, 8));
console.timeEnd(‘Binary’);

console.time('Linear');
console.log(find2PairsBySumLin(arr, 8));
console.timeEnd('Linear');

true
Binary: 4.590ms
true
Linear: 0.709ms

Here my question: Is the LinkedList approach a real linear search? After all I loop through all the nodes, while my outer loop iterates through the initial array.

Here is my LinkedList search function:

LinkedList.prototype.find = function(data) {
  var headNode = this.head;
  if(headNode === null) {
    return new Node(null);
  }
  while(headNode !== null) {
    if(headNode.data === data) {
      return true;
    } else {
      headNode = headNode.next;
    }
  }
  return false;
}
share|improve this question
    
Benchmarking on small input sizes isn't very useful. Try large inputs and many times. – nem035 20 hours ago
    
How exactly did you conclude that a nested loop has logarithmic complexity??? – Oriol 20 hours ago
up vote 0 down vote

first of all find2PairsBySumLog function is not a binary search, it's a kind of brute force method which parses all the elements of array and it's worst case time complexity should be O(n*n), and the second function is a linear search that' why you are getting the second method to run fastly, for the first function i.e. find2PairsBySumLog what you can do is initialize binary HashMap and check for every pair of integers in array kind of like you are doing in the second function probably like

bool isPairsPresent(int arr[], int arr_size, int sum)
{
  int i, temp;
  bool binMap[MAX] = {0}; 

   for (i = 0; i < arr_size; i++)
   {
     temp = sum - arr[i];
     if (temp >= 0 && binMap[temp] == 1)
          return true;
     binMap[arr[i]] = 1;
  }
}
share|improve this answer
    
We are talking about Javascript here Deepak. – Thomas Dittmar 20 hours ago
    
Hey Thomas Dittmar enough of spoon feeding man, do I had to convert this C code to javascript just to make you guys understand "Ohhh it's a javascript code yeah now i can read it". Come on man, I just gave him a hint or maybe a pseudo code kind of thing where he can just understand the logic behind his mistake – Deepak Sharma 20 hours ago
    
The only reason why I mention Javascript is because there are no inbuilt HashMaps or Hashsets. That's why I implemented my own Linked List. I also don't need to save a key and value but just the value. – Thomas Dittmar 19 hours ago
    
Okay you didn't mention that you don't want to store key value pairs but just for information every javascript object is a hashmap map , do something like var map = {}; and map[key] = value; and that' all – Deepak Sharma 19 hours ago
up vote 0 down vote

Don't use this. Use a set.

function find2PairsBySum(arr, sum) {
  var set = new Set();
  for(var num of arr) {
    if (set.has(num)) return true;
    set.add(sum - num);
  }
  return false;
}

That's all. Both add and has are guaranteed to be sublinear (probably constant) in average.

share|improve this answer
    
Of course, remember this may not work with decimals, e.g. 0.3 - 0.1 is not 0.2. – Oriol 20 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.