cuda中的二分查找
cuda中的二分查找
用户1154259
发布于 2018-01-17 18:28:21
发布于 2018-01-17 18:28:21
使用背景
通常，在做高性能计算时，我们需要随机的连接某些点。这些点都具有自己的度量值，显然，度量值越大的值随机到的概率就会越大。因此，采用加权值得方法：
void getdegreeSum(DG *g){
memset(degreeSum,0,sizeof(uint)*MAXSIZE);
uint i,last=0;
for(i=0;i<(g->n);i++){
degreeSum[i] = g->v[i].desum+last;
last = degreeSum[i];
}
}这样degreeSum[]数组中存储的即是一个有序的数组，随机生成rand(max)，随机数所在的区域的下表就代表选取到的点。
传统的二分查找函数
传统的二分查找中，是指定元素，然后查找是否在其中，典型的算法如下：
int bsearchWithoutRecursion(int array[], int low, int high, int target)
{
while(low <= high)
{
int mid = (low + high)/2;
if (array[mid] > target)
high = mid - 1;
else if (array[mid] < target)
low = mid + 1;
else //find the target
return mid;
}
//the array does not contain the target
return -1;
}其中Low与high可以根据自己的需求，来定义
cuda中的二分查找应用
问题背景：
指定的一个有序数组，给定一个随机数，要查询随机数所在的区域，即大于前一个值，小于当前值，而当前值的下标，即使所需：
实现方式：
__inline__ __device__ int binarySearch(uint *arr,uint length,uint target){
int left=0;
int right = length-1;
while(left < right){
int middle = (left+right)/2;
if((target >= arr[middle-1]) && (target < arr[middle])){ //while(rand > degreedis[j])
return middle;
}
else{
if(target > arr[middle])
left = middle+1;
else
right = middle-1;
}
}
return left;
}引用的时候，直接在__global__函数中使用即可，返回值即使要查询的下标。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2013-11-05 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录