Leetcode刷题java之33. 搜索旋转排序数组

青旅半醒 2024-04-18 12:16 54阅读 0赞

执行结果：

通过

显示详情

执行用时 :1 ms, 在所有 Java 提交中击败了99.87%的用户

内存消耗 :36.3 MB, 在所有 Java 提交中击败了85.29%的用户

题目：

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 \[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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

code:

class Solution {
        public int search(int[] nums, int target) {
            int left=0;
            int right=nums.length-1;
            int mid;
            while(left<=right)
            {
                mid=(left+right)/2;
                if(target==nums[mid])
                {
                    return mid;
                }
                //判断左边是否是递增的
                if(nums[left]<=nums[mid])
                {
                    //左边递增就先判断一下它是否在左边，如果不在，那么就是右边
                    if(target<nums[mid]&&target>=nums[left])
                    {
                        right=mid-1;
                    }else
                    {
                        left=mid+1;
                    }
                }else
                //否则，就是右边是递增的，右边递增就先判断是否在右边
                {
                    if(target>nums[mid]&&target<=nums[right])
                    {
                        left=mid+1;
                    }else
                    {
                        right=mid-1;
                    }
                }
            }
            return -1;
        }
    }