灵神基础算法精讲-05-学习笔记

162. 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

做法

定义红色为峰顶左侧元素，蓝色为峰顶或峰顶右侧元素。由于峰顶一定在数组中，所以数组最右侧的元素一定是蓝色的，那么二分的时候可以初始化左指针为0，右指针为n-2，通过比较 M 指向的数字和 M+1 指向的数字来染色，由于题目保证数字不同，所以 M 要么大于 M+1，要么小于 M-1，如果是小于，说明 M 在峰顶左侧，如果是大于，说明 M 在峰顶或峰顶右侧，最后返回 L 作为答案。

153. 寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

做法

判断nums[mid]是在最小值的左侧还是右侧，可以和最后一个数比大小，由于最小值一定在数组中，那么最后一个数要么是最小值，要么在最小值右侧(所以n-1是蓝色)，所以可以在0到n-2中二分。

如果 nums[mid] 小于最后一个数，那么 nums[mid] 有两种情况，它在一段递增数组中，或者在两段递增数组中的第二段，无论是哪种情况，nums[mid] 要么是最小值，要么在最小值右侧，这种情况下，将其染成蓝色，否则由于我们在0到n-2中二分，是不可能等于最后一个数的；那么另外一种情况就是 nums[mid] 大于最后一个数，那么 nums[mid] 就不可能在只有一段递增的情况中了，说明 nums[mid] 一定在最小值左侧，这种情况染成红色。

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, 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) 的算法解决此问题。

思路

需要在下标0到n-1上二分，分三种情况讨论，什么时候 nums[mid] 在 target 及其右侧，这种情况染成蓝色。

第一种情况：如果 nums[mid] 比最后一个数大，说明 nums[mid] 在左边这段，如果此时 target 也大于最后一个数，那么 target 和 nums[mid] 在同一段，并且如果 nums[mid] 大于等于 target，说明 nums[mid] 在 target 及其右侧，那么 mid 及其右侧就染成蓝色。

第二种情况：如果 nums[mid] 小于等于最后一个数，说明 nums[mid] 在右边这段，如果此时 target 大于最后一个数，那么 target 在左边这段，说明 mid 在target 右侧，染成蓝色。

第三种情况：如果 nums[mid] 小于等于最后一个数，说明 nums[mid] 在右边这段，如果此时 target 小于等于 nums[mid]，说明 mid 在target 右侧，染成蓝色。

做法

首先定义一个判断下标是否为蓝色的函数，函数逻辑对应思路中的三种情况，然后套用二分三种写法中的任意一种即可。