LeetCode 33.搜索旋转排序数组

1.题目

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/submissions/

2.解题思路

这道题我一开始看着的时候想法特别直接，不就是拿个数让我对比一下他在一个数组中的索引吗？我直接for+if 一遍历再一判断对比一下不就行了。可是他有时间复杂度的要求，如果是按照那个方法，时间复杂度就是O（n）。比O（logn）要大。而一看到O（logn）,直接就是二分法。这个题目只是比一般二分法要区分一下具体的两种情况，具体情况如下图：

情况一.png
情况二.png

按照上述两种情况使用二分法即可

3.代码

Java

class Solution {
    public int search(int[] nums, int target) {
        if(nums.length==1&&nums[0]==target)return 0;
        int left=0;
        int right = nums.length - 1;
        //情况分为两种：
        while (left<right){
            int mid = (left + right) / 2;
            if(target==nums[left])return left;
            if(target==nums[right])return right;
            if(target==nums[mid])return mid;
            if(nums[mid]>nums[left]){
                //1.num[mid]>num[left]
                if(target>nums[mid]){
                    left=mid+1;
                }else{
                    if(target>nums[left]){
                        right=mid-1;
                    }else{
                        left=mid+1;
                    }

                }
            }else{
                //2.num[mid]<=num[left]
                if(target>nums[mid]){
                    if(target<nums[right]){
                        left=mid+1;
                    }else{
                        right=mid-1;
                    }
                }else{
                    right=mid-1;

                }

            }
        }

        return -1;

        
    }
}

4.提交截图

33.png