每日一题:81. 搜索旋转排序数组 II

解题思路

因为是有序数列，所以使用二分搜索，又因为他是一个对某一个点进行了旋转的数组，所以我们主要进行的步骤为下

1.分情况：

如果第一个数大于target那么说明，target在下一段上升序列中，我们就需要找到下一段上升序列的开头

如果第一个数小于target那么说明，target在开头的这段上升序列中，我们需要找到这段序列的尾巴

如果第一个数就是target那么直接返回true

2.对得出的begin和end进行二分搜索

代码

二分搜索

class Solution {
    public boolean search(int[] nums, int target) {
        int begin = 0,end = nums.length-1,length = nums.length;
        if (nums[0]>target){//nums[0]已经大于target说明target在下一段上升序列中
            //找到下一段上升序列的开头
            for (int i=1;i<length;i++){
                if (nums[i]<nums[i-1]){
                    begin=i;
                    break;
                }
            }
        }
        else if (nums[0]==target){
            return true;
        }
        else if (nums[0]<target){
            //找到当前序列的结尾
            for (int i=1;i<length;i++){
                if (nums[i]<nums[i-1]){
                    end=i-1;
                    break;
                }
            }
        }
        return midSearch(nums,begin,end,target);
    }
    public boolean midSearch(int[] nums,int begin,int end,int target){
        while (begin<=end){
            int mid = (begin+end)/2;
            if (nums[mid]==target) return true;
            else if (nums[mid]>target){
                end=mid-1;
            }
            else if (nums[mid]<target){
                begin=mid+1;
            }
        }
        return false;
    }
}
           

暴力解

class Solution {
   public boolean search(int[] nums, int target) {
       int length = nums.length;
       for (int i=0;i<length;i++){
                if (nums[i]==target){
                    return true;
                }
        }
        return false;
    }
}