binary search in array of object javascript-CodePudding

I have an array of objects :

array = [
  {
    name:'alex',   
    number:36783712773
  },
  {
    name:'gabe',   
    number:99938873,
  },
and so on like this
]

I know the basic concept of binary search and how it works but most of the examples of the internet deal with an array of numbers so I cannot figure out to search by name and phone through the array of objects.

I can search from the backend but I do not want to make unnecessary http calls for a thing which can easily be dealt with in javascript.

All I want from you guys is either refer me to some tutorial which does what I want to accomplish or if you yourself can help me please do.

CodePudding user response：

I will post this as an answer: A linear search with Array#find runs quite fast for reasonable array sizes (like 10 million), and will beat a binary search implementation in JavaScript, even though the time complexity of that latter is better. This is because the linear search involves less JavaScript code, while the binary search involves more JavaScript at every step.

Here is a script that times the execution of both linear search and binary search on arrays of objects. First on an array of 1000 objects, then 10 000, then 100 000, ...etc.

In all cases up to an array size of 10 million, linear search wins (on Chrome and Firefox):

function binarySearch(array, target) {
    let lo = 0; hi = array.length;
    while (lo < hi) {
        let mi = (lo   hi) >> 1;
        let diff = target - array[mi].number;
        if (diff === 0) return array[mi];
        else if (diff < 0) hi = mi;
        else lo = mi   1;
    }
}

function linearSearch(array, target) {
    return array.find(o => o.number === target);
}

function test(searchFunc, array, searchValues, times) {
    let accTime = 0;
    for (let time = 0; time < times; time  ) { // Time the execution several times
        let now = performance.now();
        for (let number of searchValues) {
            let match = searchFunc(array, number);
            if (!match) throw "err";
        }
        accTime  = performance.now() - now;
    }
    return accTime / times; // ... and take average
}

for (let length = 1000; length < 1e8; length *= 10) {
    let array = Array.from({length}, (_, number) =>
        ({ name: "alex", ismember: true, number: number * 100   13 })
    );
    let searchValues = Array.from({length: 10000}, () =>
        Math.floor(Math.random(length)) * 100   13
    );
    // First a dry run
    let linearSearchTime = test(linearSearch, array, searchValues, 2);
    let binarySearchTime = test(binarySearch, array, searchValues, 2);
    // The real run
    linearSearchTime = test(linearSearch, array, searchValues, 5);
    binarySearchTime = test(binarySearch, array, searchValues, 5);
    console.log({length, binarySearchTime, linearSearchTime});
}