【Leetcode每日一刷】数组|704. 二分查找、27. 移除元素

力扣每日刷题

• 一、704. 二分查找
• • 1.1、题目
  • 1.2、解题思路
  • 1.3、代码实现——C++
  • 1.4、 总结&易错
• 二、27. 移除元素
• • 2.1：题目
  • 2.2、解题思路
  • 2.3、代码实现——C++
  • 1.4、 总结&易错

一、704. 二分查找

1.1、题目

704. 二分查找

1.2、解题思路

• 题型：数组、二分查找（变式）—寻找第1个大于等于目标值的元素

• 关键：二分查找的关键点就是—两边夹（高数上又叫作夹逼准则）。left和right确定答案所在区间，通过mid(把区间划分为[left,mid]&[mid+1,right]两个区间)来缩小区间范围，直到left==right,即获得答案。

  • 为什么呢？存在如下定理：A <= target <= B，当A = B时，target = A = B

• 思路：
  1.确定答案可能取值区间[left, right]
  2.left = 0;right = nums.size()-1;(因为此题中array.length也有可能为答案）
  3.while(left<right)（不考虑所谓的什么闭区间，就仅仅代表它本身的含义：当left==right时，即找到答案，跳出循环

  • 为什么呢？因为很多问题就这么设计，一定要等到最后才能确定问题的答案，在很多时候，不能在循环体中找到答案。

  4.确定循环体中分支的两种情况：

  • a.target>array[mid]：left=mid+1
  • b.else (即target<=array[mid])：right=mid

  5.left==right跳出循环体后：return array[right] == targer？right : -1;
  ????为什么呢直接return left/right呢？我们来分析一下跳出循环后的两种情况

  • 情况1：最简单的一种情况，即夹逼准则成立时，找到答案：array[left]=array[right]=targer，这个很好理解。此时array[left]==targert
  • 情况2：即没找到与target相等的元素的下标。因为array[left]<=target<=array[right]是默认恒成立的–即target应该存在于这个区间。即left指针指向[left,right]最后一个小于等于target的元素；right指针指向[left,right]第一个大于等于target的元素。在[left,right]实际区间范围不断缩小的过程中，当left和right重合时，right指向的是[0,array.length-1]这个区间第一个大于等于target的元素.（我个人目前觉得在理解层面上，return right比return left要好理解一些，虽然两者达到的效果是一样的）

1.3、代码实现——C++

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

1.4、 总结&易错

• 【易错】二分查找的重点就划分区间、逐渐缩小、两边夹，关于划分区间这题第二个代码我用的划分为[left,mid]和[mid+1,right]，为什么不是**[left,mid-1]和[mid,right]**呢？—因为会容易出现死循环

使用[left, mid-1]和[mid, right]划分区间的代码：

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

• 【重点】二分法的关键是缩小区间，死循环发生的原因是某次循环没有缩小区间导致二分失败。

• 【重点】此题right设置为array.length的原因是array.length也有可能是问题答案

• 【重点】将二分查找的判断条件写成while(left<right)，代表的是搜索区间为[left,right]，一旦left==right,即此时找到问题答案，立即跳出循环。

• 【重点】循环不变量：在[left,right]搜索答案

• 【重点】防止溢出：int mid = left + ((right - left) >> 1)/int mid = left + ((right - left + 1) >> 1)

二、27. 移除元素

2.1：题目

2.2、解题思路

这题我的想法是运用双指针：

• 左指针负责从左往右遍历，若遇到等于val的元素，停下
  • 此时右指针从右往左遍历，若遇到非val元素：将其赋值给左指针处。
• 左指针负责保证新数组为非val元素
• 右指针保证能将右侧的非val元素填充到左指针当前检测到的val元素处
• 当左右指针相等，说明左指针（包括左指针）往左即为新数组。
  

2.3、代码实现——C++

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0;
        int right = nums.size() - 1;
        while ( left <= right){
            if (nums[left] == val){
                while(nums[right] == val && right > left){
                    right --;
                }
                if(nums[right] != val){
                    //右指针找到一个非val值，并赋值给left指针所在位置
                    nums [left] = nums[right];
                    right --;
                }else{
                    break;
                }
            }
            left ++;
        }
        return left; //因为返回的是长度，所以+1
    }
};

1.4、 总结&易错

• 【易错】这题的易错点在于：在右指针向左探测，寻找非val元素时，它不一定找得到！！！当找不到时，说明此时左指针以左已经完全没有val元素，左指针和右指针之间也没有非val元素，此时就直接可以break跳出循环，结束了！