33. Search in Rotated Sorted Array

1.题目描述

英文版：

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm‘s runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0

Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3

Output: -1

中文版：

假设有一个数组是按升序进行排序，但是从某个未知的元素开始处于旋转状态。

(例如：[0,1,2,4,5,6,7] 7后面又从0开始排序，变成[4,5,6,7,0,1,2]).

从数组中找出目标元素，如果如果找到就返回其下标，如果找不到则返回-1.

假设数组中不存在重复的元素.

算法的时间复杂度必须是O(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

2.解法

2.1 解法1

思路：

    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right){
            int middle = left + (right - left) / 2 ;

            if(nums[middle] == target){
                return middle;
            }else if(nums[middle] < nums[right]){   //中间的数小于右边的数，右边有序，左边无序
                if(target > nums[middle] && target <= nums[right]){
                    left = middle + 1;
                }else {
                    right = middle - 1;
                }
            }else { //中间的数大于右边的数，左边有序，右边无序
                if(target < nums[middle] && target >= nums[left]){
                    right = middle - 1;
                }else {
                    left = left + 1;
                }
            }
        }
        return -1;
    }

在LeetCode上运行的结果：

3.测试

在本地，我只是简单写了一个main函数来对它进行测试。但是这些代码都是在LeetCode上运行通过了的。

    public static void main(String[] args) {
        int[] nums = {7,0,1,2,4,5,6};
        int target = 7;
        int result = search(nums,target);
        System.out.println(result);
    }

欢迎关注个人公众号，可直接扫描以下二维码或微信搜索“阿毛聊技术”。

33. Search in Rotated Sorted Array

原文：https://www.cnblogs.com/limaodeng/p/12353908.html