leetcode刷题（1）704. 二分查找

704. 二分查找题目链接: 704.二分查找二分法思路AcWing 算法基础课笔记【基础算法篇】2.整数二分与浮点数二分代码classSolution{public:intsearch(vectorintnums,inttarget){intl0,rnums.size()-1;while(lr){// 可以写作 mid l (r - l) / 2 作用为防止溢出等效于 (l r) / 2intmidlr1;if(nums[mid]target)rmid;elselmid1;}if(nums[l]!target)return-1;returnl;}};时间复杂度为O ( l o g n ) O(logn)O(logn)空间复杂度O ( 1 ) O(1)O(1)相似题目35.搜索插入位置代码classSolution{public:intsearchInsert(vectorintnums,inttarget){intl0,rnums.size()-1;while(lr){intmidlr1;if(nums[mid]target)rmid;elselmid1;}if(nums[l]target)returnl1;returnl;}};同样使用了二分法时间复杂度为O ( l o g O(logO(logn ) n)n)空间复杂度O ( 1 ) O(1)O(1)34. 在排序数组中查找元素的第一个和最后一个位置代码classSolution{public:vectorintsearchRange(vectorintnums,inttarget){if(!nums.size())return{-1,-1};// 要注意容器为空的情况vectorintC;intl0,rnums.size()-1;while(lr){intmidlr1;if(nums[mid]target)rmid;elselmid1;}if(nums[l]!target)return{-1,-1};C.push_back(l);l0,rnums.size()-1;while(lr){intmidlr11;if(nums[mid]target)lmid;elsermid-1;}C.push_back(l);returnC;}};同类题目AcWing 789.数的范围