面试题 10.03. 搜索旋转数组

面试题 10.03. 搜索旋转数组

题目链接：

题目描述：

搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。
arr 长度范围在[1, 1000000]之间

示例：

输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
输出: 8（元素5在该数组中的索引）

输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
 输出：-1 （没有找到）

题解：

方法一： 暴力遍历

1.思路：

解释一下什么是旋转数组：
数组的旋转就是循环移动，不管旋转多少次，一定是左边递增，中间断开，右边递增的

直接遍历所有数组

2.复杂度：

时间复杂度：O(n)
空间复杂度：O(1)

3.代码：

class Solution {
    public int search(int[] arr, int target) {
        
        // 方法一：暴力便利0
         for(int i=0 ; i<arr.length; i++){
             if(arr[i]==target){
                 return i;
             }
         }
         return -1;
        

        
        
    }
}

方法二： 二分查找

1.思路：

解释一下什么是旋转数组：
数组的旋转就是循环移动，不管旋转多少次，一定是左边递增，中间断开，右边递增的

利用上面的这个特性可以将数组分成两个有序的部分，这样就可以利用二分找出target的索引值

2.复杂度：

时间复杂度：O(logn)
空间复杂度：O(1)

3.代码：

class Solution {
    public int search(int[] arr, int target) {
        

        
//         方法二： 二分
        
        int left = 0;
        int right = arr.length-1;
        int mid=0;
        //为了消除后端与arr[0]相同的值
        while(0<=right && arr[0]==arr[right]) right--;
        if(right<0)
            return 0;
        //找最小值
        if(arr[left]>arr[right]){
            while(left<right){
                mid = (left+right)>>1;
                if(arr[0] > arr[mid]){
                    right=mid;
                }else{
                    left=mid+1;
                }  
            }
           
        }
        
        if(left==right){
            if(arr[0]>target){
                right=arr.length-1;
            }else{
                right--;
                left =0;
            }
        }
        //找target索引
        while(right>left){
            mid = (right+left)>>1;
            if(arr[mid]>=target){
                right=mid;
            }else{
                left = mid+1;
            }
        }
        return arr[right]==target?right:-1;
        
        
        
        
    }
}