leetcode 二分题 C++实现

本文主要是介绍leetcode 二分题 C++实现，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

把数组分成三个区间，[left,mid-1] mid [mid+1,right]，使用这种写法通常的情况是要找的元素的性质比较简单，直接。

704. 二分查找

简单题

时间复杂度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;
    }
};

633. 平方数之和

中等题

时间复杂度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]，把区间分成“一定不存在目标元素的区间”和“可能存在目标元素的区间”，适合于比较复杂的题目。

35. 搜索插入位置

简单题

时间复杂度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;
    }
};

参考资料：

写对二分查找不能靠模板，需要理解加练习 （附练习题，持续更新）

这篇关于leetcode 二分题 C++实现的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！