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传入的是哪一种结果未知
折腾了半天,才发现题目意思理解错了,所谓旋转并不是以数组中某个数字为轴旋转,而是以一个其它的点为圆心,这样就不存不动的数字,所有结果如下
如果直接循环遍历,复杂度是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));
}
}