二分查找

Cpp代码

int bisearch(int a[], int n, int t)  //数组a有序，长度为n， 待查找的值为t
{
    int l = 0, u = n - 1;
    while (l <= u) {
        int m = l + (u - l) / 2; //同（l+u）/ 2，这里是为了溢出
        if (t > a[m])
            l = m + 1;
        else if (t < a[m])
            u = m - 1;
        else
            return m;
    }
    return -(l+1);
}

Cpp代码  

int bsearch_first(int a[], int n, int t)
{
    int l = -1, u = n;
    while (l + 1 != u) {
        /*循环不变式a[l]<t<=a[u] && l<u*/
        int m = l + (u - l) / 2; //同（l+u）/ 2
        if (t > a[m])
            l = m;
        else
            u = m;
    }
    /*assert: l+1=u && a[l]<t<=a[u]*/
    int p = u;
    if (p>=n || a[p]!=t)
        p = -1;
    return p;
}

Cpp代码  

int bsearch_last(int a[], int n, int t)
{
    int l = -1, u = n;
    while (l + 1 != u) {
        /*循环不变式, a[l] <= t < a[u]*/
        int m = l + (u - l) / 2;
        if (t >= a[m])
            l = m;
        else
            u = m;
    }
    /*assert: l+1 = u && a[l] <= t < a[u]*/
    int p = l;
    if (p<=-1 || a[p]!=t)
        p = -1;
    return p;
}

四、旋转数组元素查找问题

题目：把一个有序数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转。现在给出旋转后的数组和一个数，旋转了多少位不知道，要求给出一个算法，算出给出的数在该数组中的下标，如果没有找到这个数，则返回-1。要求查找次数不能超过n。

分析：由题目可以知道，旋转后的数组虽然整体无序了，但是其前后两部分是部分有序的。由此还是可以使用二分查找来解决该问题的。

解法一：:2次二分查找。首先确定数组分割点，也就是说分割点两边的数组都有序。比如例子中的数组以位置2分割，前面部分{3,4,5}有序，后半部分{1,2}有序。然后对这两部分分别使用二分查找即可。代码如下：

Cpp代码  

int split(int a[], int n)
{
    for (int i=0; i<n-1; i++) {
        if (a[i+1] < a[i])
            return i;
    }
    return -1;
}

int bsearch_rotate(int a[], int n, int t)
{
    int p = split(a, n); //找到分割位置
    if (p == -1)
        return bsearch_first(a, n, t); //如果原数组有序，则直接二分查找即可
    else {
        int left = bsearch_first(a, p+1, t); //查找左半部分
        if (left == -1) {  //左半部分没有找到，则查找右半部分
            int right = bsearch_first(a+p+1, n-p-1, t); //查找右半部分
            if (right != -1) return right+p+1;  //返回位置，注意要加上p+1
            return -1;
        }
        return left; //左半部分找到，则直接返回
    }
}