javascript - Can I do a binary search on an array of objects? - Stack Overflow

admin管理员组

文章数量:1415145

I am currently learning how to use searching and sorting algorithms and I am running into issues with a binary search on an array of objects of customers' data. The array of customers is sorted by first and last name.

The goal is to find a customer's email and return the index.

The data looks like:

[
  {
    "username": "Maude.Torp",
    "email": "[email protected]",
    "address": {
      "street": "Rowe Fields",
      "suite": "Suite 231",
      "city": "Tiannamouth",
      "zipcode": "07584-6653",
      "geo": { "lat": "75.0283", "lng": "-17.1824" }
    },
    "phone": "795-827-5446 x18366",
    "website": "nico",
    "pany": {
      "name": "Champlin, Feest and Barrows",
      "catchPhrase": "Object-based user-facing orchestration",
      "bs": "transition integrated content"
    },
    "firstName": "Maida",
    "lastName": "Feeney"
  },
  ...
]

My binary search function looks like:

function searchByEmail(email, customers) {
  let start = 0;
  let end = customers.length - 1;

  while (start <= end) {
    let middle = Math.floor((start + end) / 2);

    if (customers[middle] === email) {
      return middle;
    } else if (customers[middle] < email) {
      start = middle + 1;
    } else {
      end = middle - 1;
    }
  }
  return -1;
}

On a sorted array of numbers I am able to return the index of the desired key.

let customers = [1, 10, 45, 56, 66, 567]
...
console.log(searchByEmail(66, customers))

// --> 4

When I look through this array of objects I only return -1. How do I change this algorithm to work for objects within arrays?

I am currently learning how to use searching and sorting algorithms and I am running into issues with a binary search on an array of objects of customers' data. The array of customers is sorted by first and last name.

The goal is to find a customer's email and return the index.

The data looks like:

[
  {
    "username": "Maude.Torp",
    "email": "[email protected]",
    "address": {
      "street": "Rowe Fields",
      "suite": "Suite 231",
      "city": "Tiannamouth",
      "zipcode": "07584-6653",
      "geo": { "lat": "75.0283", "lng": "-17.1824" }
    },
    "phone": "795-827-5446 x18366",
    "website": "nico.",
    "pany": {
      "name": "Champlin, Feest and Barrows",
      "catchPhrase": "Object-based user-facing orchestration",
      "bs": "transition integrated content"
    },
    "firstName": "Maida",
    "lastName": "Feeney"
  },
  ...
]

My binary search function looks like:

function searchByEmail(email, customers) {
  let start = 0;
  let end = customers.length - 1;

  while (start <= end) {
    let middle = Math.floor((start + end) / 2);

    if (customers[middle] === email) {
      return middle;
    } else if (customers[middle] < email) {
      start = middle + 1;
    } else {
      end = middle - 1;
    }
  }
  return -1;
}

On a sorted array of numbers I am able to return the index of the desired key.

let customers = [1, 10, 45, 56, 66, 567]
...
console.log(searchByEmail(66, customers))

// --> 4

When I look through this array of objects I only return -1. How do I change this algorithm to work for objects within arrays?

• javascript
• arrays
• object
• binary-search-tree

Share Improve this question Follow edited Mar 26, 2021 at 16:26 asked Mar 26, 2021 at 16:13 user14385210user14385210 5

• Is the array of customers sorted by the email address? That is what you would need to be able to do a binary search on the email. – Andrew Morton Commented Mar 26, 2021 at 16:16
• Right, same as I was about to say :) – Zorgatone Commented Mar 26, 2021 at 16:27
• Also note that if you get that big array from a database, you may want to query it with some filter, instead of retrieving all customers and then finding one or more from the plete list – Zorgatone Commented Mar 26, 2021 at 16:31
• @Zorgatone Awesome, I appreciate it. You've been super helpful! – user14385210 Commented Mar 26, 2021 at 16:35
• @alexwhitmore you're wele – Zorgatone Commented Mar 26, 2021 at 17:33

Add a ment  | 

3 Answers 3

Sorted by: Reset to default 4

You should be able to binary search the customer array, provided that it's ordered by customer email.

Change the code up a bit to pare the email instead of the entire object, accessing the email property of the object.

function searchByEmail(email, customers) {
  let start = 0;
  let end = customers.length - 1;

  while (start <= end) {
    let middle = Math.floor((start + end) / 2);

    // NOTE the ".email" part added
    if (customers[middle].email === email) {
      return middle;
    } else if (customers[middle].email < email) {
      start = middle + 1;
    } else {
      end = middle - 1;
    }
  }
  return -1;
}

You can add binary search method to Array.prototype and use it as lower_bound or upper_bound c++ equivalents. The method of array prototype will return the nearest index of an element in array.

Here is my implementation:

Array.prototype.binarySearch = function(elem, pare = (a, b) => a < b) {
  let left = 0;
  let right = this.length;

  while (left != right - 1) {
    const mid = Math.floor((left + right) / 2);
    if (pare(this[mid], elem)) {
      left = mid;
    } else {
      right = mid;
    }
  }

  return left + pare(this[left], elem);
};

// sorted array
const arr = [
  { age: 10, name: 'nick'},
  { age: 20, name: 'john'},
  { age: 30, name: 'aaron'},
  { age: 30, name: 'ana'},
  { age: 30, name: 'ana'},
  { age: 30, name: 'casandra'},
  { age: 40, name: 'dave'}, 
  { age: 40, name: 'jake'},
  { age: 50, name: 'pablo'}
];

// search by age

const lowByAge = arr.binarySearch({ age: 30 }, (a, b) => a.age < b.age);
console.log('lower_bound (age):', lowByAge); // lower_bound (age): 2

const upByAge = arr.binarySearch({ age: 30 }, (a, b) => a.age <= b.age);
console.log('upper_bound (age):', upByAge); // upper_bound (age): 6

// search by age and name

const lowByAgeAndName = arr.binarySearch({ age: 30, name: 'ana' }, (a, b) => 
    (a.age == b.age) ?  a.name < b.name : a.age < b.age);
console.log('lower_bound (age, name):', lowByAgeAndName); // lower_bound (age, name): 3

const upByAgeAndName = arr.binarySearch({ age: 30, name: 'ana' }, (a, b) => 
    (a.age == b.age) ?  a.name <= b.name : a.age < b.age);
console.log('upper_bound (age, name):', upByAgeAndName); // upper_bound (age, name): 5

Then you can use this method in any function you want.

Adding to the above answers,

Yes, We can do binary search on a sorted array of objects. But it's not the best way when it's unsorted.

If array is unsorted then you need to do 2 steps.

1. You need to sort it first (Complexity O(n))
2. You need to implement binary search(Complexity O(n))

Total plexity for above steps is O(n*n)

But to unsorted array you need to go with linear search and the plexity is O(n)

So Considering array of objects and if its sorted.

Then instead of paring each value we are going to access and pare a value which is inside the object. Remaining algorithm is as same as in Binary search.

本文标签： javascriptCan I do a binary search on an array of objectsStack Overflow