leetcode刷题--彻底弄清二分查找_冲鸭的猪的博客-爱代码爱编程
LeetCode刷题–彻底弄清二分查找
- 二分查找的时候结束条件老是令人困惑,中间的while应该加不加=呢?左边界是啥呢?右边界是啥呢?
- 其实二分查找分成两种情况
- 左闭右闭 [a,b]
- 左闭右开[a,b)
左闭右闭
【a,b】,说明里面任何一个值都可以取到,当a==b的时候也可以取到,所以那个while里面可以出现等于号。
- 当nums[mid]!=target时,边界应该缩短成[left,mid-1]或者[mid+1,right]
- 因为此时为左闭右闭区间,所以中间的值可以取到,所以很明确target不会取到nums[mid]
- 同时因为[left,right]是左闭右闭区间,所以初始化的时候分别是0和nums.length-1
class Solution {
public int search(int[] nums, int target) {
int left=0,right=nums.length-1;
while(left<=right){
int mid=(left+right)/2;
if(nums[mid]==target)
return mid;
else if(nums[mid]>target)
right=mid-1;
else
left=mid+1;
}
return -1;
}
}
左闭右开
【a,b),说明右边界不可以取到,所以a!=b,所以while里面的条件不可以出现等号
- 因为此时是左闭右开,右边界不可以取到。所以缩区间的时候应该是[left,mid)和[mid+1,right),因为是左闭右开,所以[left,mid)的mid不会取到,所以范围其实是[left,mid-1]
class Solution {
public int search(int[] nums, int target) {
//左闭右闭
int left=0,right=nums.length;
while(left<right){
int mid=(left+right)/2;
if(nums[mid]>target)
right=mid;
else if(nums[mid]<target)
left=mid+1;
else
return mid;
}
return -1;
}
}
移除元素
- 其实就是用快慢指针
- 总体思路,用慢指针存储保存的数组,用快指针遍历原来的数组,当遍历到非target元素的时候,将慢指针前进一位,然后快指针的内容填入到慢指针那里。
保存的数组,用快指针遍历原来的数组,当遍历到非target元素的时候,将慢指针前进一位,然后快指针的内容填入到慢指针那里。