lower_bound(int A*,int l,int r,int val);
對于有序數(shù)組求職為val的元素插入位置，第一個出現(xiàn)該元素的位置.
分析:
等待插入的元素是val，有序數(shù)列是A[](此處按照升序排列),尋找的范圍是[l,r];
如果查找區(qū)間只存在一個元素 l==r;時.
只需要判斷val>A[l]時返回插入下標(biāo)是l+1:
否則val<=A[l]返回的下表是l(因為要找的插入位置，小于或者相等都會插入到查找位置)
否則如果存在l<r;(l>r為不合法的情況，或者如果l>r時交換l和r)
可以取中點m=(l+r)/2;
比較A[m],與val的值的大小.
如果：
1.val>A[m];則如果A[]中存在val，那么一定是在右邊,因此令l=m+1;
2.val<A[m];則如果A[]中存在val, 那么一定是在左邊,因此令r=m-1;
3.val=A[m];則如果A[]在m之前存在val,那么一定是在左邊此時邊界保留,或者不保留,令r=m;或者r=m-1（選擇較好的m-1）
可以將二三合并為普遍情況r=m; （如果r=m-1沒查到結(jié)果會出現(xiàn)到m處查到的情況,因此可以做這樣的歸并）
如果l<r 任意的m=(l+r)/2 ? < ?(r+r)/2即為r，任意計算出的r'<r;
如果l<r 任意的m=(l+r)/2 + 1 ?> (l+l)/2 + 1 (即為l+1) l'>l;

對于任意區(qū)間范圍內(nèi)l<r;是區(qū)間都在縮小,不會出現(xiàn)死循環(huán)直到l==r;(此時問題可解) ;

一次算法描述可以是

int lower_bound(int *A,int L,int R,int val){int l=L,r=R;while(l<r){ int m=(l+r)/2;if(val<=A[m]){r=m-1;}else{l=m+1;}}return val<=A[l]?l:l+1; }以一個例子說明
A[1]={1};
此時有l(wèi)==r;
查找大值2;
由于2>A[(0+1)/2];
因此插入位置l+1,即為1;
查找相同值1；
插入位置是l,即為0.
查找小值0:
插入位置是0,即為0.


如果l<r
A[5]={1，2，2，2，2};
此時查找2 (r=m)
第i次查找
i= 1 ?2 ?3 ?4 ?
l= 0 ?0 ?0 ?1
r= 4 ?2 ?1 ?1
m= 2 ?1 ?0 ?退出循環(huán)返回l,即為1.
如果零r=m-1;
l= 0 ?0 ?1
r= 4 ?1 ?1
m= 2 ?0 ?退出循環(huán)返回1
因此可以看出將情況A[m]=val，將r=m-1，效率更高O(log2n);

upper_bound思想同理

描述可以是

int upper_bound(int *A,int L,int R,int val){int l=L,r=R;while(l<r){int m=(l+r)/2;if(val>=A[m]){l=m+1;}elser=m-1;}return val>=A[r]?r+1:r; }
int main(){int a[10]={1,2,2,2,2,2,2,4,5,6};printf("%d\n",lower_bound(a,0,9,2));printf("%d\n",upper_bound(a,0,9,2));return 0; } 執(zhí)行結(jié)果

總結(jié)

以上是生活随笔為你收集整理的c语言实现lower_bound和upper_bound的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。