Check if element exists in array without linear search

Question

Let's say I had an array containing unique values, and I wanted to check if a certain element existed:

var bannedIPs = ['0.0.0.0', '127.0.0.1', '192.168.1.1', '192.168.1.2'];
var isBanned = bannedIPs.includes('0.0.0.0'); // true

This works fine, except for the fact that it uses linear search, meaning that for an array of N elements, it would take N iterations to check if an element existed.

A much faster way to do this would be to use an object:

var bannedIPs = {'0.0.0.0': null, '127.0.0.1': null, '192.168.1.1': null, '192.168.1.2': null};
var isBanned = bannedIPs.hasOwnProperty('0.0.0.0'); // true

This method uses O(1) lookup, which is done in constant time, leading to much better performance.

However, notice how I have to store arbitrary values for the keys. Is there any other method that is potentially more suitable for this task, one that maybe doesn't require you to store values for each key?

CertainPerformance · Accepted Answer · 2021-06-26 17:03:51Z

3

Use a Set instead. Unlike an array, and unlike an object, and unlike a Map, Sets are collections of just plain values, without any associated key.

var bannedIPs = new Set(['0.0.0.0', '127.0.0.1', '192.168.1.1', '192.168.1.2']);
var isBanned = bannedIPs.has('0.0.0.0'); // true

answered Jun 26, 2021 at 17:03

CertainPerformance

373k55 gold badges354 silver badges359 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

CertainPerformance Over a year ago

The initial construction of N items in a Set is O(n), but subsequent additions/deletions/lookups in that Set is either O(1) or at least sublinear.

Unmitigated · Accepted Answer · 2021-06-26 17:03:50Z

2

You can use a Set.

var bannedIPs = new Set(['0.0.0.0', '127.0.0.1', '192.168.1.1', '192.168.1.2']);
var isBanned = bannedIPs.has('0.0.0.0');

answered Jun 26, 2021 at 17:03

Unmitigated

91.4k12 gold badges102 silver badges109 bronze badges

Collectives™ on Stack Overflow

Check if element exists in array without linear search

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related