C lower_bound的实现
基于此处的以下定义
返回指向排序范围[first，last]中第一个元素的迭代器，它不会比value更小。 使用operator <用于第一个版本或comp用于第二个版本来完成比较。
什么是lower_bound（）的C等效实现。 我知道这将是对二进制搜索的修改，但似乎无法确切地指出精确的实现。
int lower_bound(int a[], int lowIndex, int upperIndex, int e); 示例案例：
int a[]= {2,2, 2, 7 }; lower_bound(a, 0, 1,2) would return 0 --> upperIndex is one beyond the last inclusive index as is the case with C++ signature. lower_bound(a, 0, 2,1) would return 0. lower_bound(a, 0, 3,6) would return 3; lower_bound(a, 0, 4,6) would return 3;
我的尝试代码如下：
int low_bound(int low, int high, int e) { if ( low =high ) { if ( e a[mid]) return low_bound(mid+1,high,e); return low_bound(low,mid,e); }
lower_bound几乎就像进行常规二进制搜索一样，除了：
- 如果找不到该元素，则在搜索中返回当前位置，而不是返回一些空值。
- 如果找到该元素，则向左搜索，直到找到不匹配的元素。 然后将指针/迭代器返回到第一个匹配元素。
是的，它真的那么简单。 🙂
以下是upper_bound和lower_bound的等效实现。 在最坏的情况下，该算法是O（log（n）），与在最坏情况下得到O（n）的接受答案不同。
请注意，此处high索引设置为n而不是n - 1 。 这些函数可以返回超出数组范围的索引。 即，如果找不到搜索关键字，它将返回数组的大小，并且它大于所有数组元素。
int bs_upper_bound(int a[], int n, int x) { int l = 0; int h = n; // Not n - 1 while (l < h) { int mid = (l + h) / 2; if (x >= a[mid]) { l = mid + 1; } else { h = mid; } } return l; } int bs_lower_bound(int a[], int n, int x) { int l = 0; int h = n; // Not n - 1 while (l < h) { int mid = (l + h) / 2; if (x <= a[mid]) { h = mid; } else { l = mid + 1; } } return l; }
实际的C ++实现适用于所有容器。 你可以在这里找到它。
python中的lower_bound和upper_bound函数将按如下方式实现：
def binLowerBound(a, lo, hi, x): if (lo > hi): return hi mid = (lo + hi) / 2; if (a[mid] == x): return binLowerBound(a, lo, mid-1, x) elif (a[mid] > x): return binLowerBound(a, lo, mid-1, x) else: return binLowerBound(a, mid+1, hi, x) def binHigherBound(a, lo, hi, x): if (lo > hi): return lo mid = (lo + hi) / 2; if (a[mid] == x): return binHigherBound(a, mid+1, hi, x) elif (a[mid] > x): return binHigherBound(a, lo, mid-1, x) else: return binHigherBound(a, mid+1, hi, x)
我知道这是一篇非常古老的post。 但是，我正在解决一个问题，我遇到了这个post。 我想为问题添加我的迭代版本，这是最后一个答案的扩展。 我用我能想到的测试用例检查了这个。 我在C＃中附加了我的代码。
此代码适用于所有范围。 但是，范围应该在最后一个索引的第一个索引+ 1之内。 如果数组的大小为N并且将范围视为[0，N]，则搜索空间将在[0，N]内。 我知道这很明显，但它帮助我检查了一些边缘情况。
static int lower_bound(int[] a, int lo,int hi, int x) { while (lo < hi) { int mid = lo + (hi-lo) / 2; if(a[mid]==x) { /*when there is a match, we should keep on searching for the next same element. If the same element is not found, mid is considered as the answer and added to 'hi' Finally 'hi' is returned*/ if(a[mid-1]!=x) { hi=mid; break; } else hi=mid-1; } else if(a[mid]>x) hi=mid-1; else lo=mid+1; } //if element is not found, -1 will be returned if(a[hi]!=x) return -1; return hi; } static int upper_bound(int[] a, int lo,int hi, int x) { int temp=hi; while (lo < hi) { int mid = lo + (hi-lo) / 2; if(a[mid]==x) { /*this section make sure that program runs within range [start,end)*/ if(mid+1==hi) { lo=mid; break; } /*when there is a match, we should keep on searching for the next same element. If the same element is not found, mid is considered as the answer and added to 'lo'. Finally 'lo' is returned*/ if(a[mid+1]!=x) { lo=mid; break; } else lo=mid+1; } else if(a[mid]>x) hi=mid-1; else lo=mid+1; } //if element is not found, -1 will be returned if(a[lo]!=x) return -1; return lo; }
这是我使用的测试用例：
Array(a) : 1 2 2 2 2 5 5 5 5 size of the array(a) : 9
将搜索元素视为2：
upper_bound(a,0,9,2)=4, lower_bound(a,0,9,2)=1
将搜索元素视为5：
upper_bound(a,0,9,2)=8, lower_bound(a,0,9,2)=5
将搜索元素视为1：
upper_bound(a,0,9,2)=0, lower_bound(a,0,9,2)=0
将搜索元素视为5：
upper_bound(a,5,9,2)=8, lower_bound(a,5,9,2)=5
int lowerBound (int *a, int size, int val) { int lo = 0, hi = size - 1; while (lo < hi) { int mid = lo + (hi - lo)/2; if (a[mid] < val) lo = mid + 1; else hi = mid; } return lo; }