binary search in array of object javascript

Question

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 that can easily be dealt with in javascript.

thanks in advance.

Answer 1

Below an implementation of binary search.

In the previous version of this answer there was a huge bug in generating the test cases. The updated version shows the supremacy of binary search compared to a linear search, already when using small arrays.

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

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 = 10; length < 1e5; length *= 10)
{
    let array = Array.from({length}, (_, number) =>
        ({ name: "alex", ismember: true, number: number * 100 + 13 })
    );
    let searchValues = Array.from({length: 10000}, () =>
        Math.floor(length * Math.random()) * 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});
}

Different searchable properties

If you want to use binary search sometimes by one property, and sometimes by another, then you'll need to create separate "indexes" referring to your data, each sorted by the relevant property.

So for instance:

let data = [
    { name: "alex", number: 13 },
    { name: "helen", number: 10 },
    { name: "zoe", number: 11 },
    { name: "willy", number: 12 },
];

let index = Object.fromEntries(["name", "number"].map(prop => [
    prop,
    data.map(o => [o[prop], o])
        .sort(([a], [b]) => (a > b) - (a < b))
]));

function binarySearch(array, target) {
    let lo = 0, hi = array.length;
    while (lo < hi) {
        let mi = (lo + hi) >> 1;
        let key = array[mi][0]; 
        if (key === target) return array[mi][1]; // the actual data
        else if (key > target) hi = mi;
        else lo = mi + 1;
    }
}

// demo
console.log(binarySearch(index.name, "willy"));
console.log(binarySearch(index.name, "zoe"));
console.log(binarySearch(index.name, "alex"));
console.log(binarySearch(index.name, "helen"));
console.log(binarySearch(index.number, 13));
console.log(binarySearch(index.number, 12));
console.log(binarySearch(index.number, 11));
console.log(binarySearch(index.number, 10));