二分查找

题目链接LeetCode704. 二分查找

二分易错点

1. while循环中，循环条件是left < right还是left <= right
2. left每次更新是left = mid + 1还是left = mid, right每次更新是right = mid - 1还是right = mid

循环不变量(重要)

在区间搜索时，需要对区间的定义弄清楚:搜索区间的定义是在该区间内查找待搜索的元素，每一次循环都是在该区间内查找,这个区间是不变的，称为循环不变量
我们的循环条件和left、right更新就要和循环不变量有关

左闭右闭

int search(int* nums, int numsSize, int target){//写法1：左闭右闭 -> 目标元素始终在[left, right]内查找int left = 0;int right = numsSize - 1;while (left <= right) //[1,1]{int mid = (left + right) / 2;if (nums[mid] < target) left = mid + 1;else if (nums[mid] > target) right = mid - 1;else return mid;}return -1;

循环不变量是左闭右闭，查找区间始终是[left, right]

• 循环条件是left <= right ,当left==right时，待查找元素可能在这个查找区间中，因为查找区间[left, right] 满足left==right的情况
  例如left = right = 2,需要在区间[2, 2]内查找，这个区间是符合搜索区间左闭右闭的原则
• 更新条件为left = mid + 1,right - 1原因在于搜索区间始终是左闭右闭的，没有找到时说明target一定不在mid的位置，所以每次更新不需要将新的区间包含mid,而是将left，right更新为mid旁边的一个数

左闭右开

 int search(int* nums, int numsSize, int target){//写法2：左闭右开 -> [left,right) 要在这个区间内寻找targetint left = 0;int right = numsSize;while (left < right) //left = 1, right = 2 [1, 2){int mid = (left + right) / 2;if (nums[mid] > target) right = mid;else if (nums[mid] < target) left = mid + 1;else return mid;}return -1;}

循环不变量是左闭右开,搜索区间是[left, right)

• 由于是左闭右开，所以一开始的right应该是numsSize
• 循环条件是left < right,搜索区间是[left, right),所以我们一定要保证循环体中的区间是满足左闭右开的，所以left一定不能等于right，比如left = right = 2,并且区间满足左闭右开，区间就是[2, 2)，这不是一个合法的区间，但是当left = 1时，区间就是[1, 2)，这是一个合法的区间，可以在该区间内查找target
• left更新为mid + 1,right 更新为mid,搜索区间是[left, right),当nums[mid]<target，我们需要更新左区间，由于左区间是闭区间，所以左区间不需要包含mid，更新为mid+1,由于右区间是开区间，所以有区间需要包含mid，更新为mid

总结

二分法写错的原因其实主要就是对区间的定义没有理解清楚，在循环中没有始终坚持根据查找区间的定义来做边界处理。

区间的定义就是不变量，那么在循环中坚持根据查找区间的定义来做边界处理，就是循环不变量规则。

移除数组

题目：LeetCode27. 移除元素

暴力解法

int removeElement(int* nums, int numsSize, int val){//2.暴力for (int i = 0; i < numsSize; i++){if (val == nums[i]){for (int j = i + 1; j < numsSize; j++){nums[j - 1] = nums[j];}i--;//i要--一次因为后面i++了一次，保证i不动numsSize--;//数组大小减一}}return numsSize;
}

双指针

使用暴力解法的时间复杂度为O(n²),双指针可以省去一层for循环

• 快指针(fast):寻找新数组的元素 ，新数组就是不含有目标元素的数组
• 慢指针(slow):指向更新 新数组下标的位置

int removeElement(int* nums, int numsSize, int val){//1.双指针int fast = 0, slow = 0;for (fast = 0; fast < numsSize; fast++){if (nums[fast] != val){nums[slow++] = nums[fast];}}return slow;