怎么给企业制作网站,免费的编程自学软件,怎样做网站手机客户端,企业馆首先总的说一下二分搜索。如果区间具有二分性#xff0c;这个二分性不仅仅是指区间是有序的#xff0c;而是我们可以通过某一种性质将整个区间分成左区间和右区间。我们通过二分的方法去不断缩小查找的区间#xff0c;最终让区间内没有元素#xff0c;这个时候的我们就得到…首先总的说一下二分搜索。如果区间具有二分性这个二分性不仅仅是指区间是有序的而是我们可以通过某一种性质将整个区间分成左区间和右区间。我们通过二分的方法去不断缩小查找的区间最终让区间内没有元素这个时候的我们就得到了分界的边界。
二分问题的难点在于边界的处理整不好就死循环了所以我们面对二分问题要一步一步分析不要漏掉东西。
这里有两个原则大家要记住
1我们的最终目的就是让搜索区间没有一个元素
2left 的左面全都是target的right 的右面全都是target的注意这里的,不是一定的根据我们自己定的条件为主。
这两个在这里不懂没关系继续往下看就明白了。
一.全闭区间
即我们的查找区间的闭区间的这个选择也影响到了我们的循环终止条件。我们的最终目的就是让区间没有一个元素两面都是闭的我们必须要 lr 。为什么闭区间要想没有元素要让 l 与 r 错开才行。
//闭区间
int nnums.length;
int left0;
int rightn-1;while(leftright){int midleft(right-left)/2;if(nums[mid]target){leftmid1;}else{rightmid-1;}
}
可能有的问题
1.left和right的初始值为什么是这个
left和right的初始值是根据我们区间的开闭写的。如果左面是开区间left-1闭区间left0右面同理开区间rightn闭区间rightn-1。
2.那我们这么写的最终left和right分别指的下标是什么
left 的左面全都是target的right 的右面全都是target的。所以说left指的是第一个target的元素right指的是最后一个target的元素。
3.为什么left要等于mid1为什么不能等于midright也是为什么不能等于mid
还是刚刚的那句left 的左面全都是target的right 的右面全都是target的。比如我们已经知道了 nums[mid]target 了所以说mid下标的元素一定targetleft的左面都是target的所以left直接等于mid1就保证了left左面全都target。right同理。
二.半闭半开
也是大家经常在网上看到的模板的类型本人并不推荐这种写法1不1的可能在做什么模板题的时候觉得自我良好。但是二分是一种用于优化的算法一般不会单独出现在一些复杂的问题其实就很乱了。
上面是一些题外话下面才是正题。
半闭半开有两种情况左闭右开和左开右闭。
//左闭右开
int nnums.length;
int left0;
int rightn;while(leftright){int midleft(right-left)/2;if(nums[mid]target){leftmid1;}else{rightmid;}
}
//左开右闭
int nnums.length;
int left-1;
int rightn-1;while(leftright){int midleft(right-left1)/2;if(nums[mid]target){leftmid;}else{rightmid-1;}
}
可能有的问题
1.为什么上面left和right两次不同
开的那一部分是取不到的所以说我们就要多“往外”一点因为一开始要全部元素都在搜索区间里。
2.为什么两种情况left和right这个1那个-1的
我们在上一种全闭的情况时提到left 的左面全都是target的right 的右面全都是target的。这里就拿左闭右开举例。右面是开区间也就是说right指向的下标的元素不在我们的搜索区间内所以说已经满足了right 的右面全都是target的这个条件。我们此时说mid下标的这个元素target的如果是闭区间right要-1但是根据开区间的性质我们是取不到这个mid下标的元素的可以理解成无形的减了一我们就没必要再-1了直接让rightmid就行了。但是left是闭的所以要1才能保证left 的左面全都是target的。
左开右闭同理。
3.为什么在左开右闭时求mid要1
这个也是开区间影响的。在最后只剩下两个元素的时候我们求midmid一定是指向左面的下标的但是左面是开区间也就是说左面的元素不在搜索区间内不在区间怎么能判断呢所以我们mid要1。
4.结束时left指向什么right指向什么
最终left和right会重合所以这里说left或right都一样。
唉为什么会重合
因为这是一开一闭。我们最用要的是left 的左面全都是target的right 的右面全都是target的。以左闭右开为例。比如说left和right重合的时候在t下标处t下标对于的元素是target的这是一定的左区间是必的所以left左面全都是target的成立右区间是开的取不到t所以right 的右面全都是target的。
明白上面的我们就知道left和right会指向第一个target的元素。
左开右闭的left和right会指向最后一个target的元素。
5.如果区间内的元素全部target或区间内元素全部target那么left和right会指向什么
在左必右开区间中如果元素全部target我们会发现left和right会指向1这肯定是不对的应该指向0才对。
在左开右闭如果元素全部target那么我们也会发现left和right指向错误。
这就是为什么不推荐这种写法太乱了我们不仅要关注加不加一还要关注元素的问题。
三.全开区间
这是本人最推荐的一种方法这种方法没有了1-1的问题方便记忆。
int nnums.length;
int left-1;
int rightn;while(left1right){int midleft(right-left)/2;if(nums[mid]target){rightmid;}else{leftmid;}
}
简洁明了。
可能有的问题
1.循环条件为什么是left1right
还是那句话我们的最终目的就是让搜索区间没有一个元素。其实当left1right的时候区间内就没有一个元素了对不对所以说这个时候就要终止了。
2.left为什么不用1right为什么不用-1
大家如果看懂上面关于这方面的解释的话这个自己就明白了。一句话因为这是全开的。
3.结束时left指向什么right指向什么
left指向最后一个target的元素right指向第一个target的元素。
如果区间内的元素全部target那left-1right0区间内元素全部target那leftn-1rightn。
四.总结
上面加粗的问题基本上可以涵盖大家可能问到的问题如果还有问题可以在评论区讨论。还有上的条件target或target这都不是固定的根据真实情况进行修改大家理解思想就行了。一定要着重理解上面反复提到的两个原则。
