704. 二分查找

LeetCode题目

注意事项

• 什么时候能够使用二分法：有序数组 & 无重复元素
• 溢出问题：注意超出范围的时候

左闭右开写法

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

左闭右闭写法

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

27. 移除元素

LeetCode题目

注意事项

• 数组地址是连续的，不能单独删除，只能覆盖

暴力解法

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

双指针法(搞清楚双指针指出的位置是什么)

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int pointer1 = 0;
        int pointer2 = 0;
        int num = 0;
        while (pointer2 < nums.size()) {
            if (nums[pointer2] != val) {
                if (pointer1 != pointer2)
                    nums[pointer1] = nums[pointer2];
                pointer1++;
                num++;
            }
            pointer2++;
        }
        return num;
    }
};