C/C++教程

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++实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!