【面试题008】旋转数组的最小数字

【面试题008】旋转数组的最小数字

旋转数组的最小数字

输入一个递增排序的数组的一个旋转，输出这个旋转数组的最小元素，

例如｛3，4，5，1，2｝为｛1，2，3，4，5｝的一个旋转，输出这个旋转数组｛3，4，5，1，2｝的最小值；

旋转之后的数组实际上可以划分成两个有序的子数组；前面子数组的大小都大于或者等于后面子数组中的元素；

我们就可以发现实际上最小的元素就是两个子数组的分界线；在有序数组里面我们可以实现O(logn)效率的查找；

本题的数组，在一定程度上面是有序的；也可以从二分查找入手。

现在的问题是我们应该怎么利用二分查找的思路来实现近似有序的数组上面的最小元素的查找。

1.和二分查找一样，我们用两个指针分别指向数组的第一个元素和最后一个元素；

2.接着我们可以找到数组的中间的元素；

3.如果该中间元素位于前面的递增子数组中，那么此时数组中最小的元素应该位于该中间元素的后面，我们可以把第一个指针指向该中间元素，这样子可以缩小查找的范围；

4.如果该中间元素位于后面的递增子数组当中，那么此时数组中的最小元素应该位于该中间元素的前面，我们可以把第二个指针指向该中间元素，这样子同样也缩小了查找的范围；

5.不管是移动那个指针，查找范围都缩小了一半，接下来我们再用更新过后的两个指针，重新做下一轮的查找；

递归的收敛情况是：因为我们在递归的过程中我们保证第一个指针一直在左边的有序数组当中，第二个指针一直在右边的有序子数组当中，

所以收敛的时候第一个指针在左边有序子数组的最右边，第二个指针在右边有序子数组的最左边，

其实也就是第一个指针紧紧挨着第二个指针的情况，这个时候递归就应该结束了，我们也就找到了最小的元素；

特殊情况的判断：如果把一个排序数组前面的0个元素搬到了后面，及排序数组本身也是这个有序数组的一个旋转；

还有一种情况是当两个指针指向的数字及他们中间的数字三者相同的时候，我们无法判断中间的数字是位于前面的有序子数组还是后面的有序子数组，这个时候我们是没有办法通过移动两个指针来缩小查找的范围的，这个时候我们不得不利用顺序查找的方法来查找最小的元素；

MinNum.cpp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

#include <iostream>
#include <exception>
#include <cstdio>
using namespace std;

int MinInOrder(int *numbers, int index1, int index2)
{
    int result = numbers[index1];
    for(int i = index1 + 1; i <= index2; ++i)
    {
        if(result > numbers[i])
        {
            result = numbers[i];
        }
    }
    return result;
}

int Min(int *numbers, int length)
{
    if(numbers == NULL || length <= 0)
    {
        throw new std::exception();
    }

    int index1 = 0;
    int index2 = length - 1;
    int indexMid = index1;
    while(numbers[index1] >= numbers[index2])
    {
/*
* 如果index1和index2指向相邻的两个数
* 则index1指向了第一个递增子数组的最后一个数字
* index2指向了第二个子数组的第一个数字，也就是数组中的最小数字
*/
        if(index2 - index1 == 1)
        {
            indexMid = index2;
            break;
        }

        /*
         * 如果下标index1,index2,indexMid指向的三个数字相等，
         * 则只能顺序查找
         */
        indexMid = (index1 + index2) / 2;
        if(numbers[index1] == numbers[index2]
                && numbers[indexMid] == numbers[index1])
        {
            return MinInOrder(numbers, index1, index2);
        }

        /*缩小查找范围*/
        if(numbers[indexMid] >= numbers[index1])
        {
            index1 = indexMid;
        }
        else if(numbers[indexMid] <= numbers[index2])
        {
            index2 = indexMid;
        }
    }

    return numbers[indexMid];
}

int main()
{
    // 典型输入，单调升序的数组的一个旋转
    int numbers[] = {3, 4, 5, 1, 2};
    int length = sizeof(numbers) / sizeof(numbers[0]);
    int expected = 1;
    int result = 0;
    try
    {
        result = Min(numbers, length);

        for(int i = 0; i < length; ++i)
            printf("%d ", numbers[i]);

        if(result == expected)
            printf(" passed ");
        else
            printf(" failed ");
    }
    catch (...)
    {
        if(numbers == NULL)
            printf("Test passed. ");
        else
            printf("Test failed. ");
    }

    return 0;
}

运行结果：

3 4 5 1 2 passed

Makefile:

1
2
3
4
5
6
7
8
9
10
11
12

.PHONY:clean
CPP=g++
CFLAGS=-Wall -g
BIN=test
OBJS=MinNum.o
LIBS=
$(BIN):$(OBJS)
    $(CPP) $(CFLAGS) $^ -o $@ $(LIBS)
%.o:%.cpp
    $(CPP) $(CFLAGS) -c $< -o $@
clean:
    rm -f *.o $(BIN)