Binary Search in C++

Using Binary Search with Custom Data Structures

Can I use binary search with a custom data structure, and if so, how?

Abstract art representing computer programming

Yes, you can use binary search with custom data structures in C++. The key is to ensure your custom data structure supports random access iterators and is sorted according to the criteria you want to search by.

Custom Data Structure

Assume you have a custom Player struct, and you want to perform binary search based on the player's name:

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct Player {
  std::string Name;
  int Score;
};

bool comparePlayers(
  const Player& a, const Player& b) {
  return a.Name < b.Name;
}

int main() {
  std::vector<Player> Players{
    {"Aragorn", 100},
    {"Legolas", 95},
    {"Gimli", 80},
    {"Frodo", 90}
  };

  // Sort the vector of Players
  std::sort(
    Players.begin(),
    Players.end(),
    comparePlayers
  );

  // Player to search for
  Player target{"Legolas", 0};

  // Perform binary search
  bool found = std::binary_search(
    Players.begin(),
    Players.end(),
    target,
    comparePlayers
  );

  std::cout << "The player Legolas "
    << (found ? "was" : "was not") << " found";
}
The player Legolas was found

Explanation

  1. Custom Comparator: Define a comparator function comparePlayers to specify how to compare Player objects based on their names.
  2. Sorting: Use std::sort() with the custom comparator to sort the vector of players.
  3. Binary Search: Use std::binary_search() with the same comparator to search for the target player.

Binary Search with Custom Comparison

When dealing with complex comparisons or multiple criteria, ensure your comparator function aligns with the sorting order. If you need to find the exact object or its position, use std::lower_bound() or std::upper_bound():

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct Player {
  std::string Name;
  int Score;
};

bool comparePlayers(
  const Player& a, const Player& b) {
  return a.Name < b.Name;
}

int main() {
  std::vector<Player> Players{
    {"Aragorn", 100}, {"Legolas", 95},
    {"Gimli", 80}, {"Frodo", 90}
  };

  std::sort(
    Players.begin(),
    Players.end(),
    comparePlayers);

  Player target{"Legolas", 0};

  auto it = std::lower_bound(
    Players.begin(),
    Players.end(),
    target,
    comparePlayers
  );

  if (it != Players.end() &&
    it->Name == target.Name) {
    std::cout << "Object found: " << it->Name;
  } else {
    std::cout << "Object not found";
  }
}
Object found: Legolas

By ensuring your data structure supports random access and using a custom comparator, you can effectively use binary search with custom data types.

This Question is from the Lesson:

Binary Search in C++

An introduction to the advantages of binary search, and how to use it with the C++ standard library algorithms binary_search(), lower_bound(), upper_bound(), and equal_range()

Answers to questions are automatically generated and may not have been reviewed.

This Question is from the Lesson:

Binary Search in C++

An introduction to the advantages of binary search, and how to use it with the C++ standard library algorithms binary_search(), lower_bound(), upper_bound(), and equal_range()

A computer programmer
Part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

This course includes:

  • 124 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved