type
status
password
date
slug
summary
category
URL
tags
icon
旋转数组
算法原理
2.寻找旋转排序数组中的最小值（153 - 中）
题目描述：
整数数组
nums 按升序排列，数组中的值 互不相同，并按上述情形进行了多次旋转 。请你找出并返回数组中的 最小元素 示例 :
二分查找
我们考虑数组中的最后一个元素
nums[-1]：在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于 nums[-1]；而在最小值左侧的元素，它们的值一定都严格大于 num[-1]。因此，我们可以根据这一条性质，通过二分查找的方法找出最小值。-
nums[mid]<nums[-1]，这说明nums[mid]是最小值右侧的元素。
-
nums[mid]>nums[-1]，这说明nums[mid]是最小值左侧的元素。
横轴表示数组元素的下标，纵轴表示数组元素的值。图中标出了最小值的位置，是我们需要查找的目标。
综上：我们可以参照 二分查找基本原理 的模板，修改
IsBlue() 的条件。使得左侧>nums[-1]，右侧≤nums[-1]。代码实现：
3.寻找旋转排序数组中的最小值II（154 - 难）
题目描述：
整数数组
nums 按升序排列，数组中的值 可能存在重复值 。返回数组中的 最小元素 。同 剑指 Offer 11. 旋转数组的最小数字示例 :
二分查找
思路：与上题不同的是数组中可能含有重复值，由于重复元素的存在，会出现
nums[mid]=nums[-1]的情况，此时我们并不能确定 nums[mid] 究竟在最小值的左侧还是右侧，因此我们不能莽撞地忽略某一部分的元素。面对这种情况，我们可以不断缩小 nums 最右侧的区间，从 nums[-1] 缩小到nums[-2]、nums[-3]、nums[-4]。
代码实现：
4.搜索旋转排序数组（33 - 中）
题目描述：
整数数组
nums 按升序排列，数组中的值 互不相同 。给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。示例 :
方法一：先寻找最值，然后将旋转数组分成两个有序数组
最简单的做法, 找到 「153. 寻找旋转排序数组中的最小值」的索引，由此可以将数组分为升序的两段。根据 nums[0] 与 target 的关系判断 target 在左段还是右段，再对升序数组进行二分查找即可。
同样的思路可以解决「1095. 山脉数组中查找目标值」，即先找到山脉数组的峰顶「852. 山脉数组的峰顶索引」, 通过峰顶将山脉数组分为两段有序的数组，接下来就可以在有序数组中查找目标值了。
直接二分查找
对于旋转数组，我们无法直接根据
nums[mid] 与 target 的大小关系来判断 target 是在 mid的左边还是右边，因此需要「分段讨论」。- 首先通过nums[mid]和nums[0]比较，判断旋转点在mid的左侧还是右侧，进而确定有序区间在mid左边还是右边。.
- 再确定目标元素target在哪边!，根据target、mid、边缘点（最左右两侧元素）即可判断target与在mid的左侧还是右侧。
这种情况同样可以套用 二分查找模板，只不过 判断条件(
IsBlue)复杂些，代码实现：5.搜索旋转排序数组II（81 - 中）
题目描述：
旋转数组
nums 中 可能存在重复值 。请你编写一个函数来判断给定的目标值 target 是否存在于数组 nums 中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。示例 :
思路：33题+154题
时间复杂度：对于这种含重复元素的二分查找问题，最坏时间复杂度O(n)，即整个数组都是同一个数，最好时间复杂度O(nlogn)。
代码实现：
山脉题目
山脉题目与旋转数组题目相似，但是又有些不同。旋转数据的左边一定大于右边（递增数据）；山脉数据的左边不一定大于右边。旋转数据的查找条件需要与边界值进行比较，山脉数据的查找条件是
8.山脉数组的峰顶索引（852 - 易）
题目描述：
符合下列属性的数组 arr 称为 山脉数组 ：
- arr.length >= 3
- 存在 i（0 < i < arr.length - 1）使得：
- arr[0] < arr[1] < ... <arr[i-1] < arr[i]
- arr[i] > arr[i+1] > ... > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < ... <arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。
示例 :
枚举
我们可以对数组 进行一次遍历。当我们遍历到下标 i 时，如果有 ，那么 就是我们需要找出的下标。更简单地，我们只需要让 满足 即可。在遍历的过程中，我们最先遍历到的满足 的下标 一定也满足
二分查找
- arr[mid] > arr[mid + 1]：那么mid在最大值的右侧，right=mid
- arr[mid] < arr[mid + 1]：那么mid在最大值的左侧，left=mid
- arr[mid] = arr[mid+1]：这种情况不存在，所以可以添加到任意其他情况
9.山脉数组中查找目标值（1095 - 难）
题目描述：给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。如果不存在这样的下标 index，就请返回 -1。
示例 :
先寻找最值，然后将旋转数组分成两个有序数组
最简单的做法, 即先找到山脉数组的峰顶「852. 山脉数组的峰顶索引」, 通过峰顶将山脉数组分为两段有序的数组，接下来就可以在有序数组中查找目标值了。