C 中的高效二分查找實作
在排序容器中尋找元素的索引或迭代器是 C 中的基本操作。然而，標準函式庫的 std::binary_search 演算法僅傳回一個布林值，指示元素是否存在，而不是其位置。
考慮容器已排序的情況，出於效率原因，二分搜尋演算法較為可取。需要滿足此需求的實作。
自訂迭代二分搜尋
一種方法是實作自訂迭代二分搜尋演算法。以下是一個範例實作：
<code class="cpp">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
}</code>演算法使用 std::lower_bound 有效地尋找指向所搜尋元素的迭代器。如果找到的值與 val 不匹配，則傳回 end() 迭代器。
替代解決方案
另一個選擇是使用std::set，它保證元素排序並提供find(T key) 方法，該方法返回給定專案的迭代器。但是，這可能不適合需要重複元素的情況。
以上是如何在 C 中使用二分查找來尋找元素索引？的詳細內容。更多資訊請關注PHP中文網其他相關文章！
