前言

查找和排序是在程序设计中经常用到的算法。查找相对而言不外乎顺序查找、二分查找、哈希表查找和二叉排序树查找，因此只要我们掌握了这些查找技巧，然后在面对不同问题的时候就可以选择合适的查找方法解决。最重要的是，二分查找是面试时候的重点，也是面试官最喜欢考查的查找方式。

哈希表和二叉排序树查找的重点在于构建对应的数据结构而不是算法本身。哈希表主要的优点是可以在 O(1) 的时间内查找某一元素，是效率最高的查找方式，而其缺点必然是消耗额外的空间来实现哈希表。
最后，我们应该要熟练掌握插入排序、冒泡排序、归并排序和快速排序算法的实现并能比较算法之间的优劣，能够从空间复杂度、平均时间复杂度和最差时间复杂度等方面去比较它们的优缺点。

题目(旋转数组)

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组{3，4，5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小元素为1。

算法思路

为了能够充分利用旋转数组的特性，我们肯定不能采用 O(n) 时间复杂度的方式去遍历数组得到最小的那个元素(顺序查找)，那么旋转数组的特性是什么？其一是旋转后的数组一般可以划分为两个递增有序的子数组，并且前一个子数组的元素都大于后面子数组的元素；其二是最小的元素刚好是这两个子数组的分界线。那么可以考虑利用二分查找来缩小查找的范围。具体如下：

情况一：当搬运的若干个元素为0时，意味这旋转数组仍为原排序数组，那么最小的元素肯定是第一个元素；
情况二：我们给排序数组两个指针，一个指向首元素，另一个指向尾元素，接着取中点，然后先判断首元素和中点元素以及尾元素是否相等，如果相等，那么我们此时我们无法知道两个子数组谁一定会比谁更大，因此我们只能采用顺序查找的方式来返回最小的元素；否则，我们判断中点元素的值是否比首元素大，如果大，那么说明前面的子数组必定大于后面的子数组，最小值肯定在后面的子数组中，那么此时将指向首元素的指针移动到中点元素，缩小查找的范围，然后继续二分查找；如果小，那么原理相反，只需要把指向尾元素的指针移动到中点元素，继续二分查找即可。
进入二分查找的条件：二分查找数组的首元素大于其尾元素。这样说明有大于0个的元素被搬到了后面。
二分查找的结束条件：当首指针和尾指针位置相邻的时候，尾指针指向的元素即为最小的元素，此时退出循环即可。

下图为首元素、中点元素和尾元素都相等的情况(阴影部分为其中一个子数组，这种特例对于二分查找失效)：

算法实现

复杂度分析

时间复杂度

当旋转数组仍为排序数组的之后，直接去第一个元素，时间复杂度O(1)；当旋转数组采用顺序查找的时候，时间复杂度为O(n)；当旋转数组采用二分查找的时候，时间复杂度为O(logn)，所以最好的时间复杂度为O(1)，最坏时间复杂度为O(n)。

空间复杂度

空间复杂度为O(1)。

参考

<<剑指offer2>>