【代码学习笔记】二分法及其易错点

适用问题1.有序数组/区间中查找元素。问题分类1.区间左闭右闭或者是数组基本思路设置变量L和R初始L为数组开头R设置为数组大小-1。用LR/ 2来计算中点M。因为是有序数组所以当M 目标时说明M右侧比M大的数都大于目标所以M和其右侧都不用再查找令R M- 1反之则令L M 1。当LR时循环继续L R时停止。2.区间左闭右开基本思路设置变量L和R初始L为数组开头R设置为数组大小-1。用LR/ 2来计算中点M。因为是有序数组所以当M 目标时说明M右侧比M大的数都大于目标所以M和其右侧都不用再查找令R M反之则令L M 1。当LR时循环继续L R时停止。两种区间处理方式不同的原因1.结束条件分析如果区间左闭右闭则我们是允许左值等于右值即[1, 1]是被允许的所以L R循环可以继续。反之同理。2.区间右值改变分析如果区间是左闭右开当M目标时说明M和其右侧都大于目标但是因为右侧是开区间如果我们这时令R M - 1则M - 1不被包含在我们搜索区间内会漏掉M - 1位置的数。