STL中返回索引的二分查找？

Question

我需要一个二分查找函数。

我在标准库中没有找到返回已找到元素的索引且如果没找到，则返回下一个大于搜索元素的索引的按位补码的函数。

我正在寻找的是什么函数？

编辑： 我需要将一个元素插入到已排序的向量中并保持其排序。这就是为什么我需要按位取反索引。

- liran63

---

我认为std::lower_bound会给你正确的插入点，以保持你的std::vector排序。事实上，我已经使用std::vector和std::lower_bound编写了一个map实现。 - Galik

是的，你说得对。我会使用它。抱歉 :) - liran63

Answer 1

我非常确定标准库中没有包含任何与你所要求的事情完全相符的内容。

要得到你想要的结果，你可能需要从std::lower_bound或std::upper_bound开始，并将返回的迭代器转换为索引，然后如果未找到该值，则补充索引。 lower_bound将找到具有该值的第一个项目的位置，或者如果指定的值不存在，则找到第一个大于指定值的项目的位置（或.end()如果不存在更大的项目）。 upper_bound将找到指定值后面的最后一个项目的位置（再次，如果不存在更大的值，则为.end()）。

听起来你希望你的集合只包含唯一的值（即，一个值最多出现一次）。如果是这样，你可能想使用std::lower_bound。然后从yourVector.begin()中减去结果以获得索引。最后，将其指向的内容与指定的值进行比较，如果它们不相等，则补充索引。

- Jerry Coffin

---

"upper_bound会找到具有该值的最后一个项目的位置（如果有的话）"是不正确的；相反，它返回严格大于提供的值的第一个元素，如果未找到，则返回结束迭代器。 - Ashutosh Aswal

@AshutoshAswal：哎呀，完全正确。谢谢你。 - Jerry Coffin

Answer 2

据我所知，STL 没有返回已排序向量索引的简单方法，但是您可以使用以下示例函数：

/**
 * @param v - sorted vector instance
 * @param data - value to search
 * @return 0-based index if data found, -1 otherwise
*/
int binary_search_find_index(std::vector<int> v, int data) {
    auto it = std::lower_bound(v.begin(), v.end(), data);
    if (it == v.end() || *it != data) {
        return -1;
    } else {
        std::size_t index = std::distance(v.begin(), it);
        return index;
    }   
}

- Jonathan L

---

应该是std::size_t index = std::distance(v.begin(), it); if (it == v.end() || *it != data) index = ~index（即index = ~index而不是index = -1），根据liran63关于按位补码的要求。 - undefined

Answer 3

这段代码应该可以正常运行

auto itr = lower_bound(v.begin(), v.end(), key) ;
index = distance(v.begin(), itr);

std::lower_bound()的更多信息 - https://www.geeksforgeeks.org/stdlower_bound-in-c/

- UNREAL

Answer 4

使用Jonathan的答案，一个一行函数，对于我们想要知道值在哪个索引处或者如果它不存在应该在哪个索引处：

int searchInsert(vector<int>& nums, int target) {
    return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
}

- Antonin GAVREL

Answer 5

我曾经处理过一个类似的问题，需要在保持向量排序的同时插入元素。 我想出的解决方案是：修改二分搜索函数以返回应插入值的位置。

int Position(vector<int> arr, size_t size, int val)//void for commented part
{
    int start=0, middle, end=size-1;
    while(arr[start] <= arr[end])
    {
        middle = (int)((start+end+1)/2);
        if (arr[middle] < val)
        {
            start = middle+1;
        }
        else if (arr[middle] > val)
        {
            end = middle-1;
        }
        else//arr[middle]=val;
        {
            return middle;
        }
    }
    mid = (int)((start+end+1)/2);
    //arr.insert(arr.begin()+mid, val); Can I do it here? got error trying to do it.
    return mid;
}

int main()
{
    vector<int> x; cin>> val;
    mid = Position(x, x.size(), val);
    x.insert(x.begin()+mid, val);
}

- Miraz

Answer 6

使用STL，我们可以找到索引

vector<int> vec{1,2,3,4,5,6,7,8,9} ;
vector<int> :: iterator index;
index=lower_bound(vec.begin(),vec.end(),search_data);
return (index-vec.begin());

- user9543356

---

这基本上与@Jonathan的答案相同，但缺少处理“未找到”情况并且不易读。此外，return不是函数，所以无需将返回值括在括号中。 - Adrian W

Answer 7

显然，这个 "将返回按位补码" 对你很重要，但我不明白你的意思。 话说回来，查找 std::upper_bound 并查看它是否符合你的需求。

- Happy Green Kid Naps

---

我已经编辑了我的问题来回答它。std::upper_bound对我没有帮助。 - liran63

你的“编辑”并没有帮助解释按位补码。std::lower_bound应该足以满足您的需求（您是否查看了文档？） - Happy Green Kid Naps

可能liran63想要位补码，因为他们不想进行额外的检查，无论元素是否存在（因此应该插入到特定位置）。换句话说，liran63希望结果在逻辑上是struct {std::size_t index; bool exists;}，同时希望bool exists在物理上被压缩到std::size_t index的最高位。 - undefined

Answer 8

int a = 0, b = n-1;
while (a <= b) {
    int k = (a+b)/2;
    if (array[k] == x) 
    {
        // x found at index k
    }
    if (array[k] < x) a = k+1;
    else b = k-1;
}

- Yash

Answer 9

int bin_search (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator low;
  low = std::lower_bound(first,last,val);
  if(low!=last && !(val<*low)){
    return (low - first + 1);
  }else{
    return 0;
  }
}

- Sarvpriy

---

你好！你能否给我们提供更多关于你的代码如何运作以及为什么它能解决这个问题的信息？ - hat