LeetCode34 在排序数组中查找元素的第一个和最后一个位置（二分模板题，左闭右开写法）

/** @lc app=leetcode.cn id=34 lang=cpp** [34] 在排序数组中查找元素的第一个和最后一个位置*/// @lc code=start
#include<iostream>
using namespace std;
#include<vector>class Solution {
public://查找数组nums中大于等于val的第一个位置//左闭右开写法int lowerBound(vector<int>& nums,int val){int n=nums.size();int left=0,right=n;//左闭右开区间[left,right)while(left<right){// 循环不变量：// nums[left-1] < target// nums[right] >= targetint mid=left+(right-left)/2;if(nums[mid]<val) left=mid+1;// 范围缩小到 [mid+1, right)else right=mid;//范围缩小到 [left, mid)}return left;//返回 left 还是 right 都行，因为循环结束后 left == right}vector<int> searchRange(vector<int>& nums, int target) {int n=nums.size();int pos1=lowerBound(nums,target);if(pos1==n||pos1!=n&&nums[pos1]!=target){return {-1,-1};}int pos2=lowerBound(nums,target+1)-1;return {pos1,pos2};}
};

时间复杂度：O(log n)

空间复杂度：O(1)

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

 

        将nums[i]与数组中的最后一个元素nums[n-1]比较，前半段nums[i]>nums[n-1]，后半段nums[i]<=nums[n-1]。

 

class Solution {
public:int findMin(vector<int>& nums) {int n=nums.size();int left=0,right=n;while(left<right){int mid=left+(right-left)/2;if(nums[mid]>nums[n-1]) left=mid+1;else right=mid;}return nums[left];}
};

时间复杂度：O(log n)

空间复杂度：O(1)