How to check if an object with equal value is in the container in logarithmic time

Question

I want to see if an object with an equal value is in the container in logarithmic time.

I would like to have the following functions:

const a = [];

const el1 = {name: 'name1', directive: 'directive1'};
const el2 = {name: 'name2', directive: 'directive2'};
const el3 = {name: 'name3', directive: 'directive3'};
const b = {name: 'name1', directive: 'directive1'};

a.push(el1);
a.push(el2);
a.push(el3);


if(a.some(el => (el.name === b.name && el.directive === b.directive ))) {
  console.log("YES!");
} else {
  console.log("NO!");
}

This gives me the result I want. However, this time is O (N).

const s = new Set();

const el1 = {name: 'name1', directive: 'directive1'};
const el2 = {name: 'name2', directive: 'directive2'};
const el3 = {name: 'name3', directive: 'directive3'};
const b = {name: 'name1', directive: 'directive1'};

s.add(el1);
s.add(el2);
s.add(el3);

if(s.has(b)) {
  console.log("YES!");
} else {
  console.log("NO!");
}

This is O (logN), but the result is not the one I want.

So, what kind of Javascript structure can I use to print YESin the above code and have O (logN) complexity? (I do not want to implement the data structure myself)

Answer 1

You can use a card with a key by name, where the corresponding value is a set of directives:

const elements = [
    {name: 'name1', directive: 'directive1'},
    {name: 'name2', directive: 'directive2'},
    {name: 'name3', directive: 'directive3'}
];

const map = new Map(elements.map(({name}) => [name, new Set]));
elements.forEach(({name, directive}) => map.get(name).add(directive));

const b = {name: 'name1', directive: 'directive1'};

if (map.has(b.name) && map.get(b.name).has(b.directive)) {
    console.log("YES!");
} else {
    console.log("NO!");
}

Run codeHide result

Answer 2

: a , .. a[i]<a[j] , a[i].name<a[j].name || (a[i].name==a[j].name && a[i].description<a[j].description))

:

const a = [];
for (i = 0; i < 100000; i++) {
  si = String(i);
  el = {
    name: 'name' + si,
    directive: 'directive' + si
  };
  a.push(el);
}

const b = {
  name: 'name70000',
  directive: 'directive70000'
};


var c = 0; // counter 

// binary search
function binary_search(a, b) {
  c++;
  var l = 0;
  var r = a.length - 1;
  if (l > r) {
    return false;
  }
  m = Math.floor((l + r) / 2);
  if ((a[m].name < b.name) || (a[m].name == b.name && a[m].directive < b.directive)) {
    return binary_search(a.slice(m + 1), b);
  } else if ((a[m].name > b.name) || (a[m].name == b.name && a[m].directive > b.directive)) {
    return binary_search(a.slice(0, m), b);
  } else {
    return true;
  }
}



found = binary_search(a, b);
console.log(found, "in " + String(c) + " steps");

Hide result

Answer 3

Array . , ( /) , .

, : name -> directive -> third_property

name. name log n quicksort directive, third_property. , , , name, directive ..

, , : element.key = element.name + element.directive:)

Answer 4

. . O(logN).😄

---

false, (el1 b) - . b el1, O(logN), :

var orderObj = function(unordered){
   const ordered = {};
   Object.keys(unordered).sort().forEach(function(key) {
       ordered[key] = unordered[key];
    });
    return ordered;
}
Set.prototype.addIt = function(item){s.add(JSON.stringify(orderObj(item)));}
Set.prototype.hasIt = function(item){return s.has(JSON.stringify(orderObj(item)));}
    
//-------------------------------------

const s = new Set();

const el1 = {name: 'name1', directive: 'directive1'};
const el2 = {name: 'name2', directive: 'directive2'};
const el3 = {name: 'name3', directive: 'directive3'};

const b = {name: 'name1', directive: 'directive1'};
const c = {directive: 'directive3', name: 'name3'};

s.addIt(el1);
s.addIt(el2);
s.addIt(el3);

s.hasIt(b)
 ?console.log("YES!")
 :console.log("NO!");

s.hasIt(c)
 ?console.log("YES!")
 :console.log("NO!");

Hide result

---

Update:

, . c el3, script return Yes result;)