二分法精讲剖析及个人理解（通俗，适合新手）-《算法笔记》同步笔记总结与补充
二分法这一章，做题时的难度明显感觉要高于前几章
专题要点：
对二分思想的掌握与运用是这一专题的要点，个人认为，理解二分思想中的二分取值（即left,right,mid），二分判断条件（mid > key, mid < key, mid == key），二分的循环条件（left < right, left <= right），二分的返回值（return left/right, return mid）尤为重要！！！可以自己先问一下自己，这几点是否完全明白，而非模棱两可。
二分思想：
1、二分前提：二分法运用的前提条件即为有序性，因此在做题时，如果有明显的有序性，可以考虑二分法，若无明显的有序性，考虑能否将数据转化为有序的（排序或进行一些运算，比如计算自序和的运算）
2、二分取值：left，right作为区间的两个端点，根据二分判断条件进行左右移动；mid作为中点主要是用来标出要查找数据的位置，并进行二分判断的
3、二分判断条件，二分循环条件与二分返回值可以根据查找目的不同，分为两种查找方式：
①查找满足相等关系的元素是否存在
二分判断条件：由于查询元素是否存在，含义是存在返回下标，不存在则需要指明查询失败，因此需要对mid和key的大于关系，小于关系，等于关系分别处理
二分循环条件：left <= right，出现left>right的情况跳出循环，这种情况发生于当left,mid,right指向同一个数时，这个数还不是目标值，则left>right，则整个查找结束返回-1
二分返回值：若元素存在，则mid==key条件成立，返回mid，若元素不存在，出现left > right，跳出循环，返回-1
int binarySearch(int left, int right, int key)
{while(left <= right){mid = (left + right) / 2;if(mid == key){return mid;}else if(mid < key){left = mid + 1;}else{right = mid - 1;}}return - 1;
}
②查找满足不等关系的元素：
代表upper_bound(), lower_bound()函数，以lower_bound()为例
二分判断条件：由于要查找的目标不一定会存在，而我们的目的也并不是要知道其是否存在，因此只有两个判断条件（少了单独判断mid == key），而mid>=key或mid
4、二分法可解的问题类型：寻找位置与寻找值
①寻找有序序列中第一个满足某条件的元素位置（同样，最后一个满足条件的元素位置也可以完成）
②数据在某一区间上取值，寻找满足条件的数据值
//返回第一个大于等于x的元素位置
int lowerBound(int a[], int left, int right, int x)
{int mid;while(left < right){mid = (left + right) / 2;if(a[mid] >= x){right = mid;} else if(a[mid] < x){left = mid + 1;}}return left;//return right;//均可
}
//返回第一个大于x的元素位置
int upperBound(int a[], int left, int right, int x)
{int mid;while(left < right){mid = (left + right) / 2;if(a[mid] > x){right = mid;}else if(a[mid] <= x){left = mid + 1;}} return left;
}
几点注意：
1、想不清楚时画图推导
2、使用二分前要寻找有序的数据
3、解题过程中要有转化的思想，把题目转换为二分可解的问题，把数据转换为有序数据
PAT的解题思路
关于这一专题的上机训练中，题目不多，但都有值得推敲的地方，建议认认真真完成，理解题目思路，能更有效的了解二分思想
B1030
参见博客
A1010
参见博客
A1044
参见博客
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！