力扣刷题记录（c++）06
目录
34. 在排序数组中查找元素的第一个和最后一个位置
题目描述：
题目解析：
代码实现：
153. 寻找旋转排序数组中的最小值
题目描述：
题目解析：
代码实现：
题目描述：
给你一个按照非递减顺序排列的整数数组
nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值
target，返回[-1, -1]。你必须设计并实现时间复杂度为
O(log n)的算法解决此问题。
题目解析：
- 可以注意到，数组是非递减的，这道题本质上也是查找，那么就可以使用二分查找，不过在寻找左右边界时的循环在迭代上有些区别。
- 设置left=0，right=n-1，进行二分查找。
- 先找左边界：
- 如果nums[mid]>target，说明目标在左边，right更新为mid-1；
- 如果nums[mid]<target，说明目标在右边，left更新为mid+1；
- 如果nums[mid]=target，分为两种情况：
- mid=0或者nums[mid]>nums[mid-1]，说明mid为左边界；
- 否则，左边界在左边，right更新为mid-1。
- 右边界只有在如果nums[mid]=target时处理有些区别，但是大差不差。
代码实现：
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int ans1 = -1, ans2 = -1;int left = 0, right = nums.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;} else {if (mid == 0 || nums[mid - 1] < target) {ans1 = mid;break;} else {right = mid - 1;}}}left = 0;right = nums.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;} else {if (mid == nums.size() - 1 || nums[mid + 1] > target) {ans2 = mid;break;} else {left = mid + 1;}}}return {ans1, ans2};}
};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)的算法解决此问题。
题目解析：
- 根据时间复杂度的要求，极有可能可以用二分查找的方法解决这道问题。
- 那么先按照模版设置出left，right，mid。然后思考如何迭代。
- 什么情况下目标在mid右边：当nums[mid]>nums[right]时。
- 否则，目标就在mid左边，或者就是要找的最小值。
代码实现：
class Solution {
public:int findMin(vector<int>& nums) {int left = 0;int right = nums.size() - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] > nums[right]) {left = mid + 1;} else {right = mid;}}return nums[left];}
};