前言 - 引言

题目:
    一类有序数组旋转查值问题.
例如:
　　有序数组 [ 1, 2, 3, 5, 5, 7, 7, 8, 9 ] 旋转后为 [ 5, 7, 7, 8, 9, 1, 2, 3, 5 ]
如何从中找出一个值索引, not found return -1.

(同事面试时手写最简单一题, 回来和我说了一下, 就记下做个终结者系列)

这种旋转数组有个特点. 大家看图

相信大家豁然开朗了.  这里给个网上烂大街答案

//
// [1, 2, 3, 5, 5, 7, 7, 8, 9]
// 升序数组翻转后
// [5, 7, 7, 8, 9, 1, 2, 3, 5]
// 查找 value, return index, not found return -1;
//
int 
search(int a[], int len, int v) {
    int begin, end, mid;
    // 异常判断
    if (a == NULL || len <= 0)
        return -1;

    begin = 0;
    end = len;
    while (begin < end) {
        mid = (begin + end) / 2;
        if (a[mid] == v)
            return mid;
        
        if (a[begin] < a[mid]) {
            // 左边有序 [begin, mid]
            if (a[begin] <= v && v < a[mid])
                end = mid;
            else
                begin = mid + 1;
        } else if (a[begin] > a[mid]) {
            // 右边有序 [mid, end)
            if (a[mid] < v && v <= a[end - 1])
                begin = mid + 1;
            else
                end = mid;
        } else {
            ++begin;
        }
    }
    
    // 没有找到
    return -1;
}

这里使用 [begin, end) 二分法技巧. 代码支持升序旋转重复数组. 最坏情况(全重复)算法复杂度是 O(n).

不过有个问题, 如果不知道是升序 asc 还是降序 desc. 那就需要额外判断了. 

// search_sort_state - 排序状态 -1 faild, 0 desc, 1 asc
static int search_sort_state(int a[], int len) {
    int state, i, s[3];
    if (a == NULL || len <= 0)
        return -1;
    // 默认 desc 降序
    if (len == 1)
        return 0;
    // 1, 2 asc 升序, 但必须反转为 2, 1 变成降序. 因而当前降序 desc 原本就是升序 asc
    if (len == 2)
        return a[0] > a[1];
    
    // 摘取不重复的3个内容
    s[0] = a[0];

    // 开始找 s[1]
    for (i = 1; i < len; ++i) {
        if (a[i] == s[0])
            continue;
        break;
    }
    // 所有值都一样, 走默认降序
    if (i >= len)
        return 0;

    s[1] = a[i];
    // 开始找 s[2]
    while (i < len) {
        if (a[i] == s[0] || a[i] == s[1]) {
            ++i;
            continue;
        }
        break;
    }
    // 只有两个不一样的值, 走默认降序
    if (i >= len)
        return s[0] > s[1];

    s[2] = a[i];

    state = 0;
    state += s[0] > s[1] ? 1 : -1;
    state += s[1] > s[2] ? 1 : -1;
    state += s[2] > s[0] ? 1 : -1;
    return state >= 0 ? 0 : 1;
}

最后是自己想得一个排序状态判别的算法(自我感觉巧妙). 试图找出不重复三个数. 例如

  6    7    5  有 

  6 < 7   <

  7 > 5   >

  5 < 5   <

原生组合是 5   6   7

因而 < 居多是升序. > 居多是降序. (核心原因是旋转数组大小关系只改变一次)

 

正文 - 扩展

　　有了上面铺垫那我们开始码一个问题终结者代码. 希望有所感悟

// bsearch_asc - 二分查找升序查找
static int bsearch_asc(int a[], int begin, int end, int v) {
    // 简单判断
    if (begin >= end || v < a[begin] || v > a[end - 1])
        return -1;

    // 二分查找
    do {
        int mid = (begin + end) / 2;
        int val = a[mid];

        if (val == v)
            return mid;

        if (val < v)
            begin = mid + 1;
        else
            end = mid;
    } while (begin < end);

    return -1;
}

static int search_asc(int a[], int len, int v) {
    int begin = 0, end = len;
    // 异常判断
    if (begin >= end)
        return -1;

    while (begin < end) {
        int mid = (begin + end) / 2;
        if (a[mid] == v)
            return mid;
        
        if (a[begin] < a[mid]) {
            // 左边有序 [begin, mid]
            if (a[begin] <= v && v < a[mid])
                return bsearch_asc(a, begin, mid, v);
            // 右边无序, 继续循环
            begin = mid + 1;
        } else if (a[begin] > a[mid]) {
            // 右边有序 [mid, end)
            if (a[mid] < v && v <= a[end - 1])
                return bsearch_asc(a, mid + 1, end, v);
            // 左边无须, 继续循环
            end = mid;
        } else {
            ++begin;
        }
    }
    
    // 没有找到
    return -1;
}

// bsearch_desc - 二分查找降序查找
static int bsearch_desc(int a[], int begin, int end, int v) {
    // 简单判断
    if (begin >= end || v > a[begin] || v < a[end - 1])
        return -1;

    // 二分查找
    do {
        int mid = (begin + end) / 2;
        int val = a[mid];

        if (val == v)
            return mid;

        if (val > v)
            begin = mid + 1;
        else
            end = mid;
    } while (begin < end);

    return -1;
}

stati