1

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.com",
    "company": {
      "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?

Improve this question
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. Commented Mar 26, 2021 at 16:16
  • Right, same as I was about to say :) 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 complete list Commented Mar 26, 2021 at 16:31
  • @Zorgatone Awesome, I appreciate it. You've been super helpful! Commented Mar 26, 2021 at 16:35
  • @alexwhitmore you're welcome Commented Mar 26, 2021 at 17:33

3 Answers 3

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 compare 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;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

That adjustment makes sense. How would this function change if it was sorted by first and last name as opposed to being sorted by email?
It would not find the results correctly. The array must be sorted by the key on which you’d like to binary search
In the best case, sorting requires N*log(N) steps. In the worst case, a search requires N steps. Sorting an array just to search is useless imo
If you will be doing more than one search it would be worth it though
Careful with this if you're using umlauts (e.g. German ones like "ä"). In my case umlauts have to be at the end of the list that I give my JavaScript code (so after "z"), otherwise this binary search won't find the word and will return "-1" incorrectly.
|
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, compare = (a, b) => a < b) {
  let left = 0;
  let right = this.length;

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

  return left + compare(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.

Improve this answer

Comments

0

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 complexity for above steps is O(n*n)

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

So Considering array of objects and if its sorted.

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

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.