简单题
时间复杂度o(logn),空间复杂度o(1)
class Solution { public: int search(vector<int>& nums, int target) { int left=0,right=nums.size()-1; while(left<=right) { int mid=(left+right)/2; if(target>nums[mid]) { left=mid+1; } else if(target<nums[mid]) { right=mid-1; } else { return mid; } } return -1; } };
中等题
时间复杂度o(sqrt(c)),空间复杂度o(1)
class Solution { public: bool judgeSquareSum(int c) { long long left = 0, right = sqrt(c); while(left <= right) { if((left * left + right * right) == c) { return true; } else if((left * left + right * right) < c) { left++; } else { right--; } } return false; } };
把数组分成两个区间[left,mid] [mid+1,right]或[left,mid-1] [mid,right],把区间分成“一定不存在目标元素的区间”和“可能存在目标元素的区间”,适合于比较复杂的题目。
简单题
时间复杂度o(logn),空间复杂度o(1)
class Solution { public: int searchInsert(vector<int>& nums, int target) { if(target > nums[nums.size() - 1]) { return nums.size(); } int left = 0, right = nums.size() - 1; while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] < target) { left = mid + 1; } else { right = mid; } } return left; } };
参考资料:
写对二分查找不能靠模板,需要理解加练习 (附练习题,持续更新)