假设有一个排序的按未知的旋转轴旋转的数组(比如，0 1 2 4 5 6 7 可能成为 4 5 6 7 0 1 2)。给定一个目标值进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1 。你可以假设数组中不存在重复的元素。

看题解之前，可以试试→在线做题

例 1:

输入: [4, 5, 1, 2, 3] and target=1,  输出: 2.  

例 2:

输入: [4, 5, 1, 2, 3] and target=0,  输出: -1.  

[题解]

算法：二分

• 根据题目我们可以知道旋转数组实际上是两个递增数组的组成，且第一个数组中的最小值大于第二个数组的最大值
• 由于数组中不存在重复的元素，那么我们可以先找到 target 在哪个数组，再进行二分

代码思路

• 二分找到第二个数组的起始位置，即整个数组的最小值的位置 minPosition
• 通过比较 target 和第二个数组最小元素（即最后一个数）大小关系判断 target 在哪一个数组
• 对 target 所在的数组二分

复杂度分析

N 表示为 A 数组的长度

• 空间复杂度：O(N)
• 时间复杂度：O(logN)

public class Solution {     /**      * @param A: an integer rotated sorted array      * @param target: an integer to be searched      * @return: an integer      */     public int search(int[] A, int target) {         if (A == null || A.length == 0) {              return -1;          }           //找到数组最小值位置 minPosition，即第二个数组的起始位置         int minPosition = 0;          intleft = 0;          int right = A.length - 1;          while (left + 1 < right) {              int mid = left + (right - left) / 2;              if (A[mid] > A[right]) {                 left = mid;              } else {                  right = mid;              }          }                   if (A[left] < A[right]) {              minPosition = left;          } else {              minPosition = right;          }           //判断 target 在哪一个数组中         if (A[A.length - 1] < target) {              left = 0;              right = minPosition - 1;          } else {              left = minPosition;              right = A.length - 1;          }          //对 target 所在数组二分搜索         while (left + 1 < right) {              int mid = left + (right - left) / 2;              if (A[mid] < target) {                  left = mid;              } else {                  right = mid;              }          }                    if (A[left] == target) {              return left;          }          if (A[right] == target) {              return right;          }                  return -1;      } }  

点此处查看更多题解

大佬有話說 (0)