二分查找--C++实现

1. 简介

满足有序性，每次排除一半的可能性。

2. 实现

2.1 手写

int bin_search(vector<int> &arr,int v) {int hi = arr.size() - 1;int lo = 0;while ( lo <= hi){int mid = (lo + hi) >> 1;if (arr[mid] < v)lo = mid + 1;elsehi = mid - 1;}return hi;
}

2.2 STL

1. lower_bound()
   C++20之后才有
   找到第一不小于某个值的位置

• 使用

lower_bound(potions.begin(), potions.end(), tar);

• 实现

template<class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value)
{ForwardIt it;typename std::iterator_traits<ForwardIt>::difference_type count, step;count = std::distance(first, last);while (count > 0){it = first; step = count / 2; std::advance(it, step);if (*it < value){first = ++it; count -= step + 1; }elsecount = step;}return first;
}

2. upper_bound()
   找到第一个严格大于某个值的位置
   C++20之后才能用。

• 使用

upper_bound(potions.begin(), potions.end(), tar);

• 实现

template<class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value)
{ForwardIt it;typename std::iterator_traits<ForwardIt>::difference_type count, step;count = std::distance(first, last);while (count > 0){it = first; step = count / 2; std::advance(it, step);if (!(value < *it)){first = ++it;count -= step + 1;} elsecount = step;}return first;
}

3. Ref

cppreference