LeetCode-33.搜索旋转排序数组

秒速五厘米 2022-01-28 08:15 276阅读 0赞

# 题目 #

假设按照升序排序的数组在预先未知的某个点上进行了旋转。  
( 例如，数组 \[0,1,2,4,5,6,7\] 可能变为 \[4,5,6,7,0,1,2\] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。  
你可以假设数组中不存在重复的元素。

**你的算法时间复杂度必须是 O(log n) 级别。**

###### 示例 1: ######

> 输入: nums = \[4,5,6,7,0,1,2\], target = 0  
> 输出: 4

###### 示例 2: ######

> 输入: nums = \[4,5,6,7,0,1,2\], target = 3  
> 输出: -1

解题思路—**二分思想**：时间复杂度必须是 **O(log n)** 级别，查找中一定要想到用**二分法**。**数组从中间分成两部分，其中一半一定是有序的，两外一半有可能是有序，有可能是部分有序**。只需要**判断target是否在有序数组中**，如果不在有序数组中，则一定**在剩余半个数组中**。写法有**递归**和**非递归**两种。

## Java解题—非递归版 ##

class Solution {
        public int search(int[] nums, int target) {
            if(nums==null || nums.length==0)
                return -1;
    
            int left = 0, right = nums.length-1;
            while(left<=right){
                int mid = left + (right-left)/2;
                if(nums[mid]==target)
                    return mid;
    
                if(nums[mid]<nums[right]){ // 右半个数组有序
                    if(nums[mid]<target && target<=nums[right])
                        left = mid + 1;
                    else
                        right = mid - 1;
                }else{ // 左半个数组有序
                    if(nums[mid]>target && target>=nums[left])
                        right = mid - 1;
                    else
                        left = mid + 1;
                }
            }
            return -1;
        }
    }

## Java解题—递归版 ##

class Solution {
        public int search(int[] nums, int target) {
            if(nums==null || nums.length==0)
                return -1;
            return beamSearch(nums, 0, nums.length-1, target);
        }
        
        public int beamSearch(int[] nums, int left, int right, int target){
            if(left>right)
                return -1;
            int mid = left + (right-left)/2;
            if(nums[mid]==target)
                return mid;
            if(nums[mid]<nums[right]){ // 右半部分有序
                if(nums[mid]<target && target<=nums[right])
                    return beamSearch(nums, mid+1, right, target);
                else
                    return beamSearch(nums, left, mid-1, target);
            }else{ // 左半部分有序
                if(nums[mid]>target && target>=nums[left])
                    return beamSearch(nums, left, mid-1, target);
                else
                    return beamSearch(nums,mid+1, right, target);
            }
        }
    }