二分查找求上下界的两种不同算法

在学习LIS的O（nlogn）的算法时看到了二分法求下界的概念，所以回白书学习了一下

在有序表中查找元素时经常用到二分法，普通的二分查找很简单，就是不断改变区间。二分查找只适用于有序数列，时间复杂度为O(nlogn)

二分查找（迭代实现）：

int bsearch(int *A, int x, int y, int v)
{
int m;
while (x < y)
    {
        m = x + (y - x) / 2;
if (A[m] == v)
return m;
else if (A[m]>v)
            y = m;
else
            x = m + 1;
    }
return -1; //说明数列中没有v
}

接下来是重点：如果数组中有多个元素为v，上面的函数输出的是哪一个下标呢？不难想到应该是靠近中间的那一个，那么怎么求出值等于v的完整区间呢？
下面的代码为求下界的函数，当v存在时返回它出现的第一个位置。如果不存在，返回这样一个下标i：在此处插入v（原来的元素A[i],A[i+1]……全部向后移动一个位置）后序列依然有序

二分查找求下界：

int lower_bound(int *A, int x, int y, int v)
{
int m;
while (x < y)
    {
        m = x + (y - x) / 2;
if (A[m]>=v)
            y = m;
else
            x = m + 1;  //插入后前面不变，那么应该输出原后一个的下标
    }
return x; 
}

思路如下：
1.A[m]等于v,至少已经找到一个，但前面可能还有，所以区间为[x,m]
2.A[m]大于v,所求的位置不可能在后面，但可能为m，区间为[x,m]
3.A[m]小于v,所求的位置不可能在前面，也不会为m，区间为[x+1,m]
合并得到A[m]大于等于v,区间变为[x,m],A[m]小于v,区间变为[m+1,y]

类似的可以写出求上界的函数，但注意：最后求出的查找区间是左闭右开的区间[x,y)，所以求上界的函数是这样的：当v存在时返回它出现的最后一个位置的后面一个位置。如果不存在，返回这样一个下标i：在此处插入v（原来的元素A[i],A[i+1]……全部向后移动一个位置）后序列依然有序

二分查找求上界：

int lower_bound(int *A, int x, int y, int v)
{
int m;
while (x < y)
    {
m = x + (y - x) / 2;
if (A[m]<=v)
x=m+1;
else
y=m;
    }
return x; 
}