# [ACCEPTED]-Where can I get a "useful" C++ binary search algorithm?-binary-search

There is no such functions, but you can 9 write a simple one using `std::lower_bound`

, `std::upper_bound`

or `std::equal_range`

.

A simple 8 implementation could be

```
template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val)
{
// Finds the lower bound in at most log(last - first) + 1 comparisons
Iter i = std::lower_bound(begin, end, val);
if (i != end && !(val < *i))
return i; // found
else
return end; // not found
}
```

Another solution 7 would be to use a `std::set`

, which guarantees the 6 ordering of the elements and provides a 5 method `iterator find(T key)`

that returns an iterator to the 4 given item. However, your requirements might 3 not be compatible with the use of a set 2 (for example if you need to store the same 1 element multiple times).

You should have a look at `std::equal_range`

. It will return 2 a pair of iterators to the range of all 1 results.

There is a set of them:

http://www.sgi.com/tech/stl/table_of_contents.html

Search for:

On a separate 5 note:

They were probably thinking that searching 4 containers could term up more than one result. But 3 on the odd occasion where you just need 2 to test for existence an optimized version 1 would also be nice.

If std::lower_bound is too low-level for 4 your liking, you might want to check boost::container::flat_multiset. It 3 is a drop-in replacement for std::multiset 2 implemented as a sorted vector using binary 1 search.

The shortest implementation, wondering why 2 it's not included in the standard library:

```
template<class ForwardIt, class T, class Compare=std::less<>>
ForwardIt binary_find(ForwardIt first, ForwardIt last, const T& value, Compare comp={})
{
// Note: BOTH type T and the type after ForwardIt is dereferenced
// must be implicitly convertible to BOTH Type1 and Type2, used in Compare.
// This is stricter than lower_bound requirement (see above)
first = std::lower_bound(first, last, value, comp);
return first != last && !comp(value, *first) ? first : last;
}
```

From 1 https://en.cppreference.com/w/cpp/algorithm/lower_bound

```
int BinarySearch(vector<int> array,int var)
{
//array should be sorted in ascending order in this case
int start=0;
int end=array.size()-1;
while(start<=end){
int mid=(start+end)/2;
if(array[mid]==var){
return mid;
}
else if(var<array[mid]){
end=mid-1;
}
else{
start=mid+1;
}
}
return 0;
}
```

Example: Consider an array, A=[1,2,3,4,5,6,7,8,9] Suppose 8 you want to search the index of 3 Initially, start=0 7 and end=9-1=8 Now, since start<=end; mid=4; (array[mid] which 6 is 5) !=3 Now, 3 lies to the left of mid 5 as its smaller than 5. Therefore, we only 4 search the left part of the array Hence, now 3 start=0 and end=3; mid=2.Since array[mid]==3, hence 2 we got the number we were searching for. Hence, we 1 return its index which is equal to mid.

Check this function, qBinaryFind:

`RandomAccessIterator qBinaryFind ( RandomAccessIterator begin, RandomAccessIterator end, const T & value )`

Performs a binary 11 search of the range [begin, end) and returns 10 the position of an occurrence of value. If 9 there are no occurrences of value, returns end.

The 8 items in the range [begin, end) must be 7 sorted in ascending order; see qSort().

If 6 there are many occurrences of the same 5 value, any one of them could be returned. Use 4 qLowerBound() or qUpperBound() if you 3 need finer control.

Example:

`QVector<int> vect; vect << 3 << 3 << 6 << 6 << 6 << 8; QVector<int>::iterator i = qBinaryFind(vect.begin(), vect.end(), 6); // i == vect.begin() + 2 (or 3 or 4)`

The function 2 is included in the `<QtAlgorithms>`

header which is a part 1 of the Qt library.

std::lower_bound() :)

0

A solution returning the position inside 3 the range could be like this, using only 2 operations on iterators (it should work 1 even if iterator does not arithmetic):

```
template <class InputIterator, typename T>
size_t BinarySearchPos(InputIterator first, InputIterator last, const T& val)
{
const InputIterator beginIt = first;
InputIterator element = first;
size_t p = 0;
size_t shift = 0;
while((first <= last))
{
p = std::distance(beginIt, first);
size_t u = std::distance(beginIt, last);
size_t m = p + (u-p)/2; // overflow safe (p+u)/2
std::advance(element, m - shift);
shift = m;
if(*element == val)
return m; // value found at position m
if(val > *element)
first = element++;
else
last = element--;
}
// if you are here the value is not present in the list,
// however if there are the value should be at position u
// (here p==u)
return p;
}
```

More Related questions

We use cookies to improve the performance of the site. By staying on our site, you agree to the terms of use of cookies.