CODEWITHSUNDEEP
javascript
Buckets
Buckets

Reputation: 89

What is the most optimal way to check if something in an array exists?

the project I'm creating involves having an array being searched through a bunch of times, I realize that if I don't do this the most optimal way possible I might see server performance issues.

I was wondering what is the least server intensive way to find a value in an array, your help would be appreciated.

I've seen some people answer this on this website but there's mixed answers, some people say a basic for loop is best and other say indexOf and findIndex would perform better but not sure which is best or if there's a different option.

Upvotes: 2

Views: 1731

Answers (2)

Joseph Cho
Joseph Cho

Reputation: 4214

Even the most optimal search through a list would have a runtime complexity of O(n). A basic for loop would be the fastest since you could make it terminate at the first occurrence. Things get slightly more interesting when you're searching for objects.

function arrayHasObj(obj, list) {
  var i = list.length;
  while (i--) {
    if (JSON.stringify(list[i]) === JSON.stringify(obj)) {
      return true;
    }

    return false;
  };
}

Here the while loop is obviously O(n), but we also need to account for the serialization of an object to JSON. This falls out of any standard time-complexity analysis. If anyone can weigh on this please do.

Generally optimizing a search through a single array isn't necessary. There is some larger optimization that need to happen in your algorithm, or if you're truly using a large dataset you should use be querying from a database.

EDIT: Obviously a dictionary/set has its merits. The OP is specifically asking about arrays.

Upvotes: 0

Yousaf
Yousaf

Reputation: 29314

Time complexity of searching in an array of length n is O(n) whereas using a Map will give you time complexity of O(1) because you don't need to iterate over a Map to know if particular element exists in it. You can get the element by using its key.

If elements exists, it will be returned in O(1) time, otherwise you will get undefined meaning element you searched for doesn't exists in the Map

So its better to use Map instead of an array in your case.

Upvotes: 1

Related Questions