一、二分解題技巧

1、二分易錯點(diǎn)

1、循環(huán)變量

while(left < right) 還是while(left <=right)

2、判斷條件

if(num[mid] > tar) mid = right 還是 mid = right -1

2、循環(huán)不變量

[left, right]
[left, right)
(left, right]

3、左閉右閉寫法

當(dāng)時左閉右閉時，while循環(huán)里面的條件，我們可以先假設(shè)，有等號即有l(wèi)eft=right的情況，例如[1,1]這個區(qū)間，那么循環(huán)是要進(jìn)入里面的，所以要取得等號。

判斷的時候，nums[mid]>tar，那么必然tar不在右半?yún)^(qū)間，所以right=mid-1

nums[mid]<tar，那么必然tar不在左半?yún)^(qū)間，所以left=mid+1

## 模板
left=0
right=size-1
while(left<=right)
{
	int mid=(left+right)/2;
	if(nums[mid]>tar)
	{
		right=mid-1;
	}
	else if(nums[mid]<tar)
	{
		left=mid+1;
	}
	else
	{
		return mid;
	}
}
return -1;

4、左閉右開寫法

例如[1,1)，既包含1又不包含1，這是個合法的區(qū)間嗎？所以while(left < right)即可。

判斷的時候，因?yàn)閚ums[mid]>tar，所以下一次搜索的時候，區(qū)間中mid必然不會在這個左半?yún)^(qū)間，所以right=mid。
當(dāng)nums[mid]<tar，因?yàn)槭亲箝]右開，明確了tar是大于nums[mid]的，那么下一次搜索的區(qū)間的左邊界必然是left=mid+1。

right的取值也要注意，因?yàn)樵鄣膮^(qū)間是不包含右邊界的，但是還是要包含所有的數(shù)字，right相當(dāng)于變大了1，所以right=size

## 模板
left=0
right=size
while(left<=right)
{
	int mid=(left+right)/2;
	if(nums[mid]>tar)
	{
		right=mid;
	}
	else if(nums[mid]<tar)
	{
		left=mid+1;
	}
	else
	{
		return mid;
	}
}
return -1;

二、題

1、二分查找

704.二分查找

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

2、移除元素

27.移除元素

刪除元素并不是刪除，而是覆蓋，erase這個操作是O(N)的時間復(fù)雜度。
暴力法：O(N²) 的時間復(fù)雜度，兩層for循環(huán)。

// 暴力  n^2 超時了
class Solution
{
public:
    int removeElement(vector<int> &nums, int val)
    {
        int size = nums.size();
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] == val)
            {
                // 將整個剩余的數(shù)組，整體移動一位
                for (int j = i + 1; j < nums.size(); j++)
                {
                    nums[j - 1] = nums[j];// 從j -1 開始為了防止越界
                }
                i--;
                size--;
            }
        }
        return size;
    }
};

雙指針解法：O(N)
fast快指針：用來獲取新數(shù)組中的元素，新數(shù)組就是不含有目標(biāo)元素的數(shù)組
slow慢指針：用來獲取新數(shù)組中需要更新的位置文章來源地址http://www.zghlxwxcb.cn/news/detail-552399.html

class Solution
{
public:
    int removeElement(vector<int> &nums, int val)
    {
        int fast = 0;
        int slow = 0;
        for (fast = 0; fast < nums.size(); fast++)
        {
        	// 不是我們需要找尋的元素，就更新原數(shù)組
            if (nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
            // 找到 nums[fast]==val 我們就不執(zhí)行更新操作，而是直接變成fast++
        }
        return slow;
    }
};

到了這里，關(guān)于代碼隨想錄day1 | 704.二分查找 27.移除元素的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！