33.搜索旋转排序数组 - Java 二分查找

原题地址：https://leetcode.cn/problems/search-in-rotated-sorted-array/

题解

参照官方题解思路

• 若[begin,mid]为有序，且nums[begin]<=target<=nums[mid]，则在[begin,mid]中查找，反之则在[mid,end]中查找
• 若[mid,end]为有序，且nums[mid]<=target<=nums[end]，则在[mid,end]中查找，反之则在[begin,mid]中查找
• 若[begin,end]有序且target不在[nums[begin],nums[end]]的范围内，则说明数组中不存在target，返回-1

时间复杂度：O(logN)

空间复杂度：O(1)

class Solution {
    public int search(int[] nums, int target) {
        return binSearch(nums,target,0, nums.length-1);
    }

    int binSearch(int[] nums,int target,int begin,int end){
        if(end<begin)return -1;
        if(nums[begin]<=nums[end]&&(target<nums[begin]||target>nums[end]))return -1;
        else{
            int mid=(begin+end)/2;
            if(nums[mid]==target)return mid;
            else if(nums[begin]<=nums[mid]){
                if(nums[begin]<=target&&target<=nums[mid]){
                    return binSearch(nums,target,begin,mid-1);
                }else{
                    return binSearch(nums,target,mid+1,end);
                }
            }
            else{
                if(nums[mid]<=target&&target<=nums[end]){
                    return binSearch(nums,target,mid+1,end);
                }else{
                    return binSearch(nums,target,begin,mid-1);
                }
            }
        }
    }
}