返回信息流输入为：有序数组经过任意旋转后的数组
输出：旋转点对应下标
示例如下
[10,11,12,15,20,21,22,3]
7
[12,15,20,21,22,3,10,11]
5
[20,21,22,3,10,11,12,15]
3
时间复杂度要求O(logn)，小白不会做，求助大神[ema1]
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #97477同步于 2019/1/6
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【问题】【求助】有序旋转数组的旋转点查找
monte2591
2019/1/6镜像同步20 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
找到那个旋转点的条件时什么呢？
【 在 zd11024 的大作中提到: 】
: 先判断初始是不是有序(比较第一个和最后一个)，然后二分，每次拿二分值和第一个数字比较。如果大于等于第一个，答案在右边。如果小于第一个，答案在左边
这道题我是知道的，但我不是求target的下标，我想求的是那个旋转点的坐标
【 在 lance6716 的大作中提到: 】
: https://leetcode.com/problems/search-in-rotated-sorted-array/
我的解法 二分查找数组中最大点 即 array[i]>array[i+1]这个i(如果不存在，返回-1） 那么最小值就是array[i+1]
class Solution {
public static int findMin(int[] nums) {
return nums[findMinHelper(nums, 0, nums.length - 1) + 1];
}
private static int findMinHelper(int[] nums, int i, int j) {
if(i == j)
return -1;
if(i == j - 1) {
if(nums[i] > nums[j])
return i;
else
return -1;
}
int center = (i + j) / 2;
if(center < nums.length - 1 && nums[center] > nums[center + 1])
return center;
int left = findMinHelper(nums, i, center);
int right = findMinHelper(nums, center, j);
if(left == -1 &&j == -1)
return -1;
if(left != -1)
return left;
if(right != -1)
return right;
return -1;
}
}