用二分查找法刷leetcode算法题目的时候,经常遇到视频看着理解很透彻,当上手写时一看就会,一写就废。二分查找法涉及边界条件很多,逻辑很简单,就是写不好。何时写 while(left<right),while(left<=right),还是 right=mid 还是right = mid - 1;等等, 其实我们只要控制区间是左闭右开、还是左闭右闭的条件,定义在区间循环变量不变的原则。
介绍 左闭右开 左闭右闭 这两种写法。
题目:leetcode704
思路:
数组是有序且数据无重复元素,返回下标就唯一,使用二分法的前提条件。若数据中重复元素,返回的下标就不唯一呢。
1、左闭右闭
定义target在左闭右闭区间中**[left, right]中,使用while(left <= right)**的循环条件,即left==right的条件是有意义的![在这里插入图
2、左闭右开
int left = 0;int right = numsSize; // 定义target在[left, right) 闭区间中while(left < right) // 当left == right 是无意义的,条件不成立,我们是取不到右边的值,使用 < 号{int mid = left + (right - left) /2; // 防止整数溢出if(nums[mid] == target) { // 找到目标值返回当前下标return mid;} else if(nums[mid] > target) {right = mid; // target在左区间中 在[left, mid)的区间中} else if (nums[mid] < target) {left = mid + 1; // target在右区间中 在[mid+1, right)的区间中}}return -1; // 在当前的区间中没有找到
}
二、双指针
双指针理解: 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
快指针:寻找新数组的元素 ,新数组就是不含有目标元素的数组
慢指针:指向更新 新数组下标的位置
题目 leetcode27
对i–,示例2中,对nums[3]覆盖nums[2],导致nums[3]在原数组有下标3变成下标2.但是i向前走了一位,需要保持i原地不动。
使用双指针:
思路:
1、定义两个指针,用fastIndex遍历与val的值,若存在不相等,用fastIndex对应的下标覆盖val。并移动slowIdex
int fastIndex = 0;int slowIndex = 0;for(fastIndex; fastIndex < numsSize; fastIndex++){if(nums[fastIndex] != val){nums[slowIndex++] = nums[fastIndex];}}return slowIndex;
leetcode977
思路:
1、定义两个指针,一个指向头,另外一个指向尾。若nums[left] * nums[left] < nums[right] * nums[right], 需要将right–,前移。反之 left++