程序员面试题精选100题（42）-旋转数组的最小元素[算法] (2)

        indexMid = (index1 + index2) / 2;

        if(numbers[indexMid] >= numbers[index1])

            index1 = indexMid;

        else if(numbers[indexMid] <= numbers[index2])

            index2 = indexMid;

    }

 

    return numbers[indexMid];

}

由于我们每次都把寻找的范围缩小一半，该算法的时间复杂度是O(logN)

值得注意的是，如果在面试现场写代码，通常我们需要用一些测试用例来验证代码是不是正确的，我们在验证的时候尽量能考虑全面些。像这道题，我们出来最简单测试用例之外，我们至少还需要考虑如下的情况：

1.              把数组前面的0个元素从最前面搬到最后面，也就是原数组不做改动，根据题目的规则这也是一个旋转，此时数组的第一个元素是大于小于或者等于最后一个元素的；

2.              排好序的数组中有可能有相等的元素，我们特别需要注意两种情况。一是旋转之后的数组中，第一个元素和最后一个元素是相等的；另外一种情况是最小的元素在数组中重复出现

3.              在前面的代码中，如果输入的数组不是一个排序数组的旋转，那将陷入死循环。因此我们需要跟面试官讨论是不是需要判断数组的有效性。在面试的时候，面试官讨论如何验证输入的有效性，能显示我们思维的严密性。本文假设在调用函数Min之前，已经验证过输入的有效性了。

最后需要指出的是，如果输入的数组指针是非法指针，我们是用异常来做错误处理。这是因为在这种情况下，如果我们用return来结束该函数，返回任何数字都不是正确的。关于无效输入时的函数如何返回错误信息并结束，本博客第17题有更详细的讨论，可以参考。