LeetCode 33:Search in Rotated Sorted Array

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

 

一开始题目旋转的意思没看太明白,其实它的意思是首先有一个已经从小到大排序号的数组,然后根据数组中某一个数字来将数组进行旋转,也就是两边进行交换,生成一个新的数组,也就是nums,然后在这个nums里查找target的值,返回index

比如,按照上面例子中的数组,简单画一下旋转大致有以下几种结果,但具体参数nums传入的是哪一种结果未知

NewImage

 

折腾了半天,才发现题目意思理解错了,所谓旋转并不是以数组中某个数字为轴旋转,而是以一个其它的点为圆心,这样就不存不动的数字,所有结果如下 

NewImage

 如果直接循环遍历,复杂度是O(n),而题目要求是O(logn),肯定还是得用二分法相关的,主要是判断target是在哪边,先找下特点

1:找到中间的数字nums[middle],如果nums[middle]==target,直接返回middle

2:如果nums[middle] >= nums[left],比如上图0,1,2,3,4的情况,这时候可以发现,左侧的都是有序的,那么假如target在左侧区间范围里,right = middle – 1;否则在右侧区间范围里,left = middle +1

3:如果nums[middle] < nums[left],比如上图5,6,7的情况,这时候可以发现,右侧的都是有序的,那么假如target在右侧区间范围里,left = middle + 1;否则在左侧区间范围里,right = middle -1

4:如果已上最终还无法找到target,返回-1

源码如下

package com.lihuia.demo;

import org.springframework.boot.autoconfigure.SpringBootApplication;

@SpringBootApplication
public class DemoApplication {

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[left]) {
if (nums[left] <= target && target < nums[middle]) {
right = middle - 1;
} else {
left = middle + 1;
}
} else {
if (nums[middle] < target && target <= nums[right]) {
left = middle + 1;
} else {
right = middle - 1;
}
}
}
return -1;
}

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

发表评论