CODEWITHSUNDEEP
c++search
user2373198
user2373198

Reputation: 147

Is there any library for binary Search in C++

Is there any pre-implemented library in C++ for fast search in a list like binary search? Does the normal list support any kind of find function? Or any function like exists?

I have a list of objects, I want to store them in a list, but not duplicate elements. I want to notice whether or not the new element exists in the list and do a proper action.

Upvotes: 0

Views: 1446

Answers (4)

Vlad from Moscow
Vlad from Moscow

Reputation: 311010

Container list is not adopted for ordering storing of elements and for their direct access. Though standard class std::list has member functions sort nevertheless the search using bidirectional iterators (std::listhas bidirectional iterators) instead of random access iterators is not very effective..

It would be better if you would use some associative container as for example std::map or std::set (if you need unique elements) or std::multimap or std::multiset (if elements can be duplucated).

if the order of elements is not important then you could use some standard unordered container as std::unordered_map or std::unordered_set

Upvotes: 0

Josh Davis
Josh Davis

Reputation: 6831

I believe you are looking for the C++ <algorithm> library. It includes a function called binary_search.

An example of it is provided on the page and echoed here:

// binary_search example
#include <iostream>     // std::cout
#include <algorithm>    // std::binary_search, std::sort
#include <vector>       // std::vector

bool myfunction (int i,int j) { return (i<j); }

int main () {
  int myints[] = {1,2,3,4,5,4,3,2,1};
  std::vector<int> v(myints,myints+9);                         // 1 2 3 4 5 4 3 2 1

  // using default comparison:
  std::sort (v.begin(), v.end());

  std::cout << "looking for a 3... ";
  if (std::binary_search (v.begin(), v.end(), 3))
    std::cout << "found!\n"; else std::cout << "not found.\n";

  // using myfunction as comp:
  std::sort (v.begin(), v.end(), myfunction);

  std::cout << "looking for a 6... ";
  if (std::binary_search (v.begin(), v.end(), 6, myfunction))
    std::cout << "found!\n"; else std::cout << "not found.\n";

  return 0;
}

Upvotes: 2

Dietmar K&#252;hl
Dietmar K&#252;hl

Reputation: 153840

There is std::lower_bound() which finds a suitable position in any bidirectional sequence using O(log n) comparisons. Since linked lists don't support random access traversal is O(n). You can use std::binary_search() if you are only interested whether there is a suitable object but this algorithm isn't useful if you are interested in locating the object. Of course, a precondition for std::lower_bound() and std::binary_search() is that the sequence is sorted.

Upvotes: 4

Alessandro Suglia
Alessandro Suglia

Reputation: 1927

If you are writing real C++ code you can use the algorithm standard library.

In it there is the find function which grant to you to look for a specific element defined between a range of element specified as a parameter.

You can find a real example in the same page.

Upvotes: 1

Related Questions