我需要一个二分查找函数。
我在标准库中没有找到返回已找到元素的索引且如果没找到,则返回下一个大于搜索元素的索引的按位补码的函数。
我正在寻找的是什么函数?
编辑: 我需要将一个元素插入到已排序的向量中并保持其排序。这就是为什么我需要按位取反索引。
我需要一个二分查找函数。
我在标准库中没有找到返回已找到元素的索引且如果没找到,则返回下一个大于搜索元素的索引的按位补码的函数。
我正在寻找的是什么函数?
编辑: 我需要将一个元素插入到已排序的向量中并保持其排序。这就是为什么我需要按位取反索引。
/**
* @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;
}
}
std::size_t index = std::distance(v.begin(), it); if (it == v.end() || *it != data) index = ~index
(即index = ~index
而不是index = -1
),根据liran63关于按位补码的要求。 - undefined这段代码应该可以正常运行
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/
使用Jonathan的答案,一个一行函数,对于我们想要知道值在哪个索引处或者如果它不存在应该在哪个索引处:
int searchInsert(vector<int>& nums, int target) {
return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
}
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);
}
使用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());
return
不是函数,所以无需将返回值括在括号中。 - Adrian Wstruct {std::size_t index; bool exists;}
,同时希望bool exists
在物理上被压缩到std::size_t index
的最高位。 - undefinedint 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;
}
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;
}
}
std::lower_bound
会给你正确的插入点,以保持你的std::vector
排序。事实上,我已经使用std::vector
和std::lower_bound
编写了一个map
实现。 - Galik