Is it possible to perform a binary search on a collection of objects in an array?

Question

Is it possible to perform a binary search on a collection of objects in an array?

As I delve into the world of searching and sorting algorithms, I've encountered a challenge with implementing a binary search on an array of customer objects. This particular array is sorted by both first and last name.

The objective here is to locate a customer's email address within the data set and retrieve its corresponding index.

A snippet of the data structure is shown below:

[
  {
    "username": "Maude.Torp",
    "email": "<a href="/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="94c0f5edf5badff1e6f8e1fff1a1a7d4f3f9f5fdf8baf7fbf9">[email protected]</a>",
    "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"
  },
  ...
]

The current implementation of my binary search function is as follows:

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;
}

While this function works for sorted arrays of numbers by returning the index of the desired key, it only outputs -1 when applied to arrays of objects like the one described above. Any tips on adjusting this algorithm to accommodate object searches?

javascript arrays object binary-search-tree

Answer 1

Answer №1

To efficiently search the customer array using binary search, make sure it is sorted by customer email.

Modify the code to compare emails instead of the entire object, focusing on the email property within each object.

function findCustomerByEmail(email, customers) {
  let startIndex = 0;
  let endIndex = customers.length - 1;

  while (startIndex <= endIndex) {
    let middleIndex = Math.floor((startIndex + endIndex) / 2);

    // Note the addition of ".email"
    if (customers[middleIndex].email === email) {
      return middleIndex;
    } else if (customers[middleIndex].email < email) {
      startIndex = middleIndex + 1;
    } else {
      endIndex = middleIndex - 1;
    }
  }
  return -1;
}

Answer 2

To efficiently search the customer array using binary search, make sure it is sorted by customer email.

Modify the code to compare emails instead of the entire object, focusing on the email property within each object.

function findCustomerByEmail(email, customers) {
  let startIndex = 0;
  let endIndex = customers.length - 1;

  while (startIndex <= endIndex) {
    let middleIndex = Math.floor((startIndex + endIndex) / 2);

    // Note the addition of ".email"
    if (customers[middleIndex].email === email) {
      return middleIndex;
    } else if (customers[middleIndex].email < email) {
      startIndex = middleIndex + 1;
    } else {
      endIndex = middleIndex - 1;
    }
  }
  return -1;
}

Answer 3

Answer №2

You have the option to integrate a binary search method into Array.prototype, enabling you to utilize it as equivalents to lower_bound or upper_bound in C++. This custom array prototype method will determine and return the closest index of an element within the array.

Below is my personalized implementation:

Array.prototype.binarySearch = function(target, 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], target)) {
      left = mid;
    } else {
      right = mid;
    }
  }

  return left + compare(this[left], target);
};

// array sorted by age
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'}
];

// searching based on 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

// searching based on 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

Now you can incorporate this method in any function of your choice.

Answer 4

You have the option to integrate a binary search method into Array.prototype, enabling you to utilize it as equivalents to lower_bound or upper_bound in C++. This custom array prototype method will determine and return the closest index of an element within the array.

Below is my personalized implementation:

Array.prototype.binarySearch = function(target, 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], target)) {
      left = mid;
    } else {
      right = mid;
    }
  }

  return left + compare(this[left], target);
};

// array sorted by age
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'}
];

// searching based on 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

// searching based on 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

Now you can incorporate this method in any function of your choice.

Answer 5

Answer №3

Expanding on the previous responses,

A sorted array of objects can indeed be subjected to binary search. However, this method is less efficient when dealing with unsorted arrays.

In the case of an unsorted array, two steps are required:

The array must be sorted first (O(n) complexity)
Then implement binary search (O(n) complexity)

The total complexity of these steps combined is O(n*n).

Alternatively, for an unsorted array, linear search is more suitable with a complexity of O(n).

When handling an array of objects that is already sorted, the process involves accessing and comparing values within each object instead of directly comparing values in the array elements. The core algorithm remains similar to binary search.

Answer 6

Expanding on the previous responses,

A sorted array of objects can indeed be subjected to binary search. However, this method is less efficient when dealing with unsorted arrays.

In the case of an unsorted array, two steps are required:

The array must be sorted first (O(n) complexity)
Then implement binary search (O(n) complexity)

The total complexity of these steps combined is O(n*n).

Alternatively, for an unsorted array, linear search is more suitable with a complexity of O(n).

When handling an array of objects that is already sorted, the process involves accessing and comparing values within each object instead of directly comparing values in the array elements. The core algorithm remains similar to binary search.

Is it possible to perform a binary search on a collection of objects in an array?

Answer №1

Answer №2

Answer №3

Similar questions

Using an array to substitute a string in JavaScript

Accessing struct array members is not possible by using pointer index

The DataTable is encountering difficulties with processing JSON data retrieved from the database

How can I cancel or reset a timeInterval in AngularJS?

Increase the value of $index within the ng-repeat loop

Is there a way to selectively update specific keys within existing objects in Mongodb without affecting the rest of the

What advantages do interfaces as data types offer in Angular compared to using classes?

Is it possible to use Node.js child processes without carriage returns?

How to update a dynamic list or array in Flutter using setState()?

The struggle of encoding: Making a JSON ajax call (utf-8) to convert Latin1 characters to uppercase

Firebase causing API to render only upon typing initiation

Updating the values of parent components in Vue.js 3 has been discovered to not function properly with composite API

Building routes for a stationary website with Angular

retrieving data from array elements

Request to api.upcitemdb.com endpoint encountering CORS issue

Placing a freshly created item into a designated array while ensuring it is positioned at Index Value [0] rather than at [arr.length-1]

Ensure that the link's color remains constant and remove any styling of text-decoration

Discovering complimentary number sequences amidst intersecting number sequences

Object-oriented programming in JavaScript allows for the passing of variables to a parent class using $

Error encountered when auto-generating IDs in Next.js with Firebase Firestore database