本文共 1022 字,大约阅读时间需要 3 分钟。
一、普通二分查找
int bin_ser(int *a, int size, int key){ int mid, l, r; l = 0; r = size-1; while(l <= r){ mid = l + (r-l)/2; if(a[mid] < key) l = mid+1; if(a[mid] > key) r = mid-1; else{ return mid; } }}
二、查找下界(大于等于key的第一个位置)没找到返回数组长度
int low_bound(int *a, int size,int key){ int l = 0, r = size-1; int mid, pos; while(l < r){ mid = l + (r-l)/2; if(a[mid] < key){ l = mid+1; pos = l; } else{ r = mid; pos = r; } } if(a[pos] > key || a[pos] == key) return pos; return pos+1;}
三、查找上界(大于 key 的第一个位置)没找到返回数组最后元素下标
int upp_bound(int *a, int size, int key){ int l = 0, r = size; int mid, pos; while(l < r){ mid = l + (r-l)/2; if(a[mid] <= key){ l = mid+1; pos = l; } else{ r = mid; pos = r; } }// if(a[pos] > key)// return pos;// return pos+1; return pos;}
注意 和 low_bound区分 这里 size取的是数组长度 不是size-1 如果取 size-1就要 用注释部分 这里 为了区分 low_bound部分采用了size-1
这样做 是因为当查找到最后条件都没找见时候 满足 left < right 右侧是size-1左侧 此时最多取到size-1就出去了 ,也就是 最后数组最后一个元素没有被查找
所以 出while循环后需要判断 是否最后一个满足条件 不满足返回数组最后元素下一个位置(数组长度)满足就返回最后元素的下标
转载地址:http://cmimi.baihongyu.com/