33. 搜索旋转排序数组

刺骨的言语ヽ痛彻心扉 2022-09-09 09:53 155阅读 0赞

[https://leetcode-cn.com/problems/search-in-rotated-sorted-array/][https_leetcode-cn.com_problems_search-in-rotated-sorted-array]

难度中等1544收藏分享切换为英文接收动态反馈

整数数组 `nums` 按升序排列，数组中的值 **互不相同** 。

在传递给函数之前，`nums` 在预先未知的某个下标 `k`（`0 <= k < nums.length`）上进行了 **旋转**，使数组变为 `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]`（下标 **从 0 开始** 计数）。例如， `[0,1,2,4,5,6,7]` 在下标 `3` 处经旋转后可能变为 `[4,5,6,7,0,1,2]` 。

给你 **旋转后** 的数组 `nums` 和一个整数 `target` ，如果 `nums` 中存在这个目标值 `target` ，则返回它的下标，否则返回 `-1` 。

**示例 1：**

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

**示例 2：**

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

**示例 3：**

输入：nums = [1], target = 0
    输出：-1

**提示：**

*  `1 <= nums.length <= 5000`
 *  `-10^4 <= nums[i] <= 10^4`
 *  `nums` 中的每个值都 **独一无二**
 *  题目数据保证 `nums` 在预先未知的某个下标上进行了旋转
 *  `-10^4 <= target <= 10^4`

**进阶：**你可以设计一个时间复杂度为 `O(log n)` 的解决方案吗？

class Solution {
        public int search(int[] nums, int target) {
            if(nums.length==1 && nums[0]==target) return 0;
            int x = 0;
            int ans =-1;
            for(int i=0;i<nums.length-1;i++)
            {
                if(nums[i+1]<nums[i]) x++;
                if(nums[i+1]==target) ans = i+1;
                if(nums[i]==target) ans = i;
            }
            if(x>1) ans = -1;
            return ans;
        }
    }

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_19_color_FFFFFF_t_70_g_se_x_16][]

[https_leetcode-cn.com_problems_search-in-rotated-sorted-array]: https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/43bad936e6d1473d819b9b7895a654cb.png