文章目录

• • 1. 二维数组中的查找
  • 2. 寻找峰值
  • • 方法一：寻找最大值
    • 方法二：二分法
  • 3. 旋转数组的最小数字

1. 二维数组中的查找

我们可以从矩阵 array 的右上角 (0,n−1) 进行搜索。在每一步的搜索过程中，如果我们位于位置 (r,l)，那么我们希望在以 array 的左下角为左下角、以 (r,l) 为右上角的矩阵中进行搜索，即行的范围为 [r,m−1]，列的范围为 [0,l]：

• 如果 array[r,l]=target，说明搜索完成；
• 如果 array[r,l]>target，由于每一列的元素都是升序排列的，那么在当前的搜索矩阵中，所有位于第 l 列的元素都是严格大于 target 的，因此我们可以将它们全部忽略，即l–；
• 如果 array[r,l]

class Solution {public:bool Find(int target, vector> array) {int r = 0;int n = array[0].size();int l = n - 1;int m = array.size();while (r < m && l >= 0) {if (array[r][l] == target) {return true;} else if (array[r][l] < target) {r++;} else {l--;}}return false;}
};

2. 寻找峰值

方法一：寻找最大值

由于题目保证了 nums[i] !=nums[i+1]，那么数组 nums 中最大值两侧的元素一定严格小于最大值本身。因此，最大值所在的位置就是一个可行的峰值位置。我们对数组 nums 进行一次遍历，找到最大值对应的位置即可。但是这种方法的时间复杂度是O(n)，不满足题目要求。

class Solution {public:int findPeakElement(vector& nums) {// write code herereturn max_element(nums.begin(), nums.end()) - nums.begin();}
};

方法二：二分法

如果我们固定选取 m 为 [l,r] 的中点，那么每次可行的下标范围会减少一半，成为一个类似二分查找的方法，时间复杂度为 O(logn)。

• 如果nums[m] > nums[m+1]，则在m之前一定存在峰值元素；
• 如果nums[m] < nums[m+1]，则在m+1之后一定存在峰值元素

class Solution {public:int findPeakElement(vector& nums) {// write code hereint l = 0;int r = nums.size() - 1;while(l < r){int m = (l + r) / 2;if(nums[m] > nums[m - 1] && nums[m] > nums[m + 1]){return m;}else if(nums[m] > nums[m + 1]){r = m;}else{l = m + 1;}}return l;}
};

3. 旋转数组的最小数字

使用二分法解决，需要考虑三种情况：

• array[mid] > array[high]：此时最小数字一定在mid的右边。low = mid + 1
• array[mid] == array[high]：此时最小数字不好判断在mid左边还是右边，这时只好一个一个试，high = high - 1
• array[mid] < array[high]：此时最小数字一定就是array[mid]或者在mid的左边。因为右边必然都是递增的。high = mid

注意这里有个坑：如果待查询的范围最后只剩两个数，那么mid 一定会指向下标靠前的数字
比如 array = [4,6]
array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ;
如果high = mid - 1，就会产生错误， 因此high = mid
但情形(1)中low = mid + 1就不会错误

class Solution {
public:int minNumberInRotateArray(vector rotateArray) {int l = 0;int r = rotateArray.size() - 1;while(l <= r){int m = (l + r) / 2;if(rotateArray[m] > rotateArray[r]){l = m + 1;}else if(rotateArray[m] == rotateArray[r]){r = r - 1;}else{r = m;}}return rotateArray[l];}
};