704.二分查找

左闭右闭

第一次的代码，陷入死循环

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

            }
        }
        return -1;
    }
};

左右范围更新有问题，因为我们的区间是左闭右闭，所以直接令right/left = mid的时候，实际上是重复检测了mid。

改进之后的代码

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

左闭右开

这是第一次的代码,直接由上面修改得到,但是在数组中只有一个元素的时候会报错,原因还是区间问题

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

将int right = nums.size() - 1;该为int right = nums.size();即可

27.移除元素

暴力法写半天结果都不对,误打误撞写出来快慢指针了

class Solution
{
public:
    int removeElement(vector<int> &nums, int val)
    {
        int numsSize = nums.size();
        int finalSize = numsSize;
        int j = 0;
        for (int i = 0; i < numsSize; i++)
        {
            if (nums[i] != val) {
                nums[j] = nums[i];
                j += 1;
            } else {
                finalSize -= 1;
            }
        }
        return finalSize;
    }
};