LeetCode-33 搜索旋转排序数组
> 题目：33. 搜索旋转排序数组
> 难度：中等
> 分类：数组
> 解决方案：二分查找
题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7]可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -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分析
这是一个二分查找的变形题，对于二分查找不太熟悉的小伙伴可以查看『数据结构与算法—二分查找（一）』。
这道题与传统的二分查找不同的是，给定的数组是一个旋转排序数组。我们先分析一下什么是旋转排序数组，如下图所示
我们称红色部分的7和绿色部分的0为旋转区域，即排序数组分割区域。我们对上面任意一个旋转数组进行查找给定值，如示例1为对上面的旋转数组4查找给定值0，查找过程如下所示：
上述分析所对应的 java代码如下所示：
class Solution { public int search(int[] nums, int target) { if(nums == null || nums.length == 0) return -1;
int low = 0, high = nums.length - 1; while (low <= high){ int mid = low + (high - low) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < nums[high]){ if (nums[mid] < target && nums[high]>=target){ low = mid + 1; }else{ high = mid - 1; } }else{ if (nums[mid] > target && nums[low] <= target){ high = mid - 1; }else { low = mid + 1; } } }
return -1; }}
Github地址
LeetCode-33 搜索旋转排序数组：https://github.com/JacobLei/leetcode/blob/master/src/main/java/A33_SearchinRotatedSortedArray.java
参考链接
搜索旋转排序数组：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-06-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录