JAVA练习339- 搜索旋转排序数组

题目概览整数数组nums按升序排列数组中的值互不相同。在传递给函数之前nums在预先未知的某个下标k0 k nums.length上进行了向左旋转使数组变为[nums[k], nums[k1], ..., 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。你必须设计一个时间复杂度为O(log 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示例 3输入nums [1], target 0输出-1提示1 nums.length 5000-10^4 nums[i] 10^4nums中的每个值都独一无二题目数据保证nums在预先未知的某个下标上进行了旋转-10^4 target 10^4来源33. 搜索旋转排序数组 - 力扣LeetCode解题分析方法二分法我们可以先尝试进行二分以 [5,6,0,1,2,3,4] 为例第一次二分之后的子数组为 [ 5,6,0,1 ] 和 [ 2,3,4]这样得到的子数组至少有一个时递增的令中间索引为 mid开始索引为 i结束索引为 j那么当 nums[ mid ] target 时返回 mid当 nums[ mid ] target 时看左子数组是否为递增数组nums[ i ] nums[mid] )若是则看 nums[ i ] 是否小于等于 target 若小于等于 target 则在左子数组中j mid - 1大于 target 则还在右边数组中i mid 1;若不是说明右子数组是递增数组target 还在左边数组中j mid - 1当 nums[ mid ] target 时看右子数组是否为递增数组nums[ j ] nums[mid] )若是则看 nums[ j ] 是否大于等于 target 若大于等于 target 则在右子数组中i mid 1小于 target 则还在右边数组中j mid - 1;若不是说明左子数组是递增数组target 还在右边数组中i mid 1时间复杂度O(logn)空间复杂度O(1)class Solution { public int search(int[] nums, int target) { int n nums.length; int i 0, j n-1; while(i j) { int mid (i j) / 2; if (nums[mid] target) { return mid; } if (nums[mid] target) { if (nums[i] nums[mid] nums[i] target) { i mid 1; } else { j mid - 1; } } else { if (nums[j] nums[mid] nums[j] target) { j mid - 1; } else { i mid 1; } } } return -1; } }