C基础 旋转数组查找题目

前言 - 引言

题目:
    一类有序数组旋转查值问题.
例如:
　　有序数组 [ 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;
}

static int search_desc(int a[], int len, int v) {
    int begin = 0, end = len;

    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_desc(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_desc(a, mid + 1, end, v);
            // 左边无须, 继续循环
            end = mid;
        } else {
            ++begin;
        }
    }
    
    // 没有找到
    return -1;
}

// 
// 题目:
//     一类有序数组旋转查值问题.
// 例如:
//     有序数组 [ 1, 2, 3, 5, 5, 7, 7, 8, 9 ] 旋转后为 [ 5, 7, 7, 8, 9, 1, 2, 3, 5 ]
// 如何从中找出一个值索引, not found return -1.
int 
search_upgrade(int a[], int len, int v) {
    int state, i, s[3];
    if (a == null || len <= 0)
        return -1;
    // 默认 desc 降序
    if (len == 1) {
        if (a[0] == v)
            return 0;
        return -1;
    }

    if (len == 2) {
        if (a[0] == v)
            return 0;
        if (a[1] == v)
            return 1;
        return -1;
    }

    // 摘取不重复的3个内容
    s[0] = a[0];

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

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

    // desc 降序, 旋转
    if (state >= 0)
        return search_desc(a, len, v); 
    // asc 升序, 旋转
    return search_asc(a, len, v);
}

不同分支不同代码, 针对性强. 代码最坏的情况是 o(n).

 

这里不妨来个测试演示

#include <stdio.h>
#include <stdlib.h>

#define len(a) (sizeof(a)/sizeof(*a))

// print - 数据内容打印
#define int_br (15)
static void print(int a[], int len) {
    int i = 0; 
    while (i < len) {
        printf(" %d", a[i]);
        if (!(++i % int_br))
            putchar('\n');
    }
    if (i % int_br)
        putchar('\n');
}

int search_upgrade(int a[], int len, int v);

// sort - 旋转查找
int main(int argc, char * argv[]) {
    int i, v;
    int a[] = { 5, 7, 7, 8, 9, 1, 2, 3, 5 };
    print(a, len(a));
    // 开始测试
    v = 8;
    i = search_upgrade(a, len(a), v);
    printf("%d -> %d\n", v, i);

    v = 5;
    i = search_upgrade(a, len(a), v);
    printf("%d -> %d\n", v, i);

    v = 6;
    i = search_upgrade(a, len(a), v);
    printf("%d -> %d\n", v, i);

    v = 7;
    i = search_upgrade(a, len(a), v);
    printf("%d -> %d\n", v, i);

    v = 4;
    i = search_upgrade(a, len(a), v);
    printf("%d -> %d\n", v, i);

    int b[] = { 7, 6, 5, 3, 3, 2, 1, 9, 9, 8, 8, 7, 7 };
    print(b, len(b));
    // 开始测试
    v = 8;
    i = search_upgrade(b, len(b), v);
    printf("%d -> %d\n", v, i);

    v = 5;
    i = search_upgrade(b, len(b), v);
    printf("%d -> %d\n", v, i);

    v = 6;
    i = search_upgrade(b, len(b), v);
    printf("%d -> %d\n", v, i);

    v = 7;
    i = search_upgrade(b, len(b), v);
    printf("%d -> %d\n", v, i);

    v = 4;
    i = search_upgrade(b, len(b), v);
    printf("%d -> %d\n", v, i);

    return exit_success;
}

当前输出结果如下

$ gcc -g -wall sort.c ; ./a.out
 5 7 7 8 9 1 2 3 5
8 -> 3
5 -> 0
6 -> -1
7 -> 2
4 -> -1
 7 6 5 3 3 2 1 9 9 8 8 7 7
8 -> 10
5 -> 2
6 -> 1
7 -> 0
4 -> -1

 

后记 - 感谢

        错误是难免的 ~ 欢迎指正 : )

        - https://music.163.com/#/song?id=493042772