面试高频算法题:搜索旋转排序数组

2019-06-0522:20:13数据结构与算法Comments2,027 views字数 1442阅读模式

搜索旋转排序数组文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

搜索一个给定的目标值 target,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是 O(log n) 级别。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

解答文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

为了方便讲解,这里我们把数组中的最小值称之为旋转点吧。接下来我们就以上面中的例子来进行讲解。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

没有旋转之前的数组文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

面试高频算法题:搜索旋转排序数组

旋转之后的数组文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

面试高频算法题:搜索旋转排序数组

显然,这个旋转点是最特殊的点,因为旋转点既比左边的数小,同时也比右边的数小。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

我们知道,在我们平时的二分查找中(也就是数组没有旋转之前),我们会把目标值 target 与 中间元素 mid 进行比较,每次比较都会有如下三种结果文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

(1)如果 target 比 mid 小,那么 mid 以及 mid 右边的所有元素一定比 target 大,所以 target 只能存在于 mid 的左边元素中。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

(2)如果 target 比 mid 大,那么 mid 以及 mid 左边的所有元素一定比 target 小,所以 target 只能存在于 mid 的右边元素中。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

(3)如果 target 与 mid 相等,则直接把 mid 对应的下标返回即可。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

而在这道题中,情况要比这个复杂,因为它还有受旋转点的位置所影响,具体可以分为以下两种情况。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

这里我在强调一下,二分查找的结果就是要把范围缩小一般,所以我们的目的就是,寻找出 target 究竟是位于 mid 的左边还是右边。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

(一)情况1:中间元素在旋转点的左侧文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

面试高频算法题:搜索旋转排序数组

(1)target 在 mid 的左边。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

面试高频算法题:搜索旋转排序数组

如果 target 在 mid 的左边,显然需要满足条件:最左边元素 >= target > mid文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

(2)taeget 在 mid 的右边文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

面试高频算法题:搜索旋转排序数组

如果不满足(1)的条件,则意味着在右边文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

(二)情况2:中间元素在旋转点的右侧或者和旋转点重合文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

右侧文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

面试高频算法题:搜索旋转排序数组

重合文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

面试高频算法题:搜索旋转排序数组

(1)target 在 mid 的 右边文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

面试高频算法题:搜索旋转排序数组

显然,需要满足的条件是 mid > target >= 最右侧元素文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

(1)target 在 mid 的左边文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

面试高频算法题:搜索旋转排序数组

如果不满足 (1) 中的条件,则在左边。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

当然,在上面的情况中,我们没有 mid 与 target 相等的情况,因为如果他们相等的话,就直接返回下边即可,无需讨论。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

上面的各种情况我们都讨论好了,下面我们直接按照上面的逻辑来写代码即可,代码如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html

int rotatedBinarySearch(int[] arr, int target){
 // 最左侧元素下标
 int left = 0;
 // 最右侧元素下标
 int right = arr.length - 1;
 while(left >= right){
 // 中间元素下标
 int mid = left + (right - left) / 2;
 if(arr[mid] == target){
 return mid;
 }
 // 情况1:如果中间元素在旋转点左侧
 if(arr[mid] <= arr[left]){
 //target 如果位于中间元素的左侧
 if(arr[mid] < target && target <= arr[left]){
 right = mid - 1;
 }else{
 left = mid + 1;
 }
 }
 // 情况2:中间元素在旋转点的右侧
 else{
 // target 如果位于中间元素的右侧
 if(arr[mid] > target && target >= arr[right]){
 left = mid + 1;
 }else{
 right = mid - 1;
 }
 }
 }
 return -1;
}
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13441.html
  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/13441.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定