一、观看PPT教程
【01】二分法
二、练习题（不清楚回头查看有关PPT）
【01】分治法的有关描述，请改正错误的地方：
分治思想——分治字面上的解释是“分而治之”，分治思想就是把一个复杂的问题分成两个或更多的与原问题相同或相似的规模较小子问题，同样再把子问题分成更小的子问题.....直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在计算机科学中，分治法就是运用分治思想的一种很重要的算法。分治法的应用——把一个复杂的问题分成两个相同或相似的子问题，就是二分法。典型的应用就是二分查找算法。类似的还有三分法、四分法。
【02】有关二分查找算法，如果有错误，请改正：
二分查找算法概念——二分查找算法（英语：binary search algorithm），也称折半搜索算法（英语：half-interval search algorithm）、对数搜索算法（英语：logarithmic search algorithm）， 是一种在有序数组中快速查找某一特定元素的搜索算法。二分查找算法思想——二分搜索先比较有序数组的中位元素和目标值。1．如果在某一步骤区间为空／无效，则说明目标值找不到。2．如果目标值与中位元素相等，则返回其在数组中的位置；3．如果目标值小于中位元素，则在数组的左半部分继续搜索。4．如果目标值大于中位元素，则在数组右半部分继续搜索。因此，每一次比较都使搜索范围缩小一半。二分查找算法步骤——给定一个有序数组A，有A[0]≤A[1]≤...≤A[n-1]，要查找目标值T。二分查找算法的一般步骤如下：设L为查找范围的左边界，R为右边界，M为中间位置。①令L＝0，R＝n-1。②如果L＞R，则此步查找失败，结束此问题。③令M＝（L＋R）／ 2。④如果A［M］＝T，查找完成，返回结果。⑤如果 A［M］＜ T，令L＝M＋1，回到步骤②。如果A［M］＞T，令R＝M-1，回到步骤 ②。
【02】下面是二分查找算法模板代码（递归），请改正错误的地方：
·
·
·
·
·
·
·
·
·
·
·
int binary_search(int arr[], int left, int right, int key){ if(left > right)return -1; int mid = left +(right - left)/2; if(arr[mid] == ley) return mid; else if (key < arr[mid]) return binary_search(arr, mid + 1, right, key); else return binary_search(arr, left, mid -1 , key);}
【03】下面是二分查找算法模板代码（循环），请改正错误的地方：
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
int binary_search(int arr[], int left, int right, int key){ int ret = -1; int mid; while(left <= right){ mid = left + (right - left) / 2; if(arr[mid] == key){ ret = mid; } else if (key > arr[mid]) left = mid +1; else right = mid - 1; } return ret; }
【04】给定一个升序的数组，查找第一个等于key的下标，找不到返归-1。例如：在数组{1,2,2,3,4}中查找2，返回1。请改正错误的地方：
·
·
·
·
·
·
·
·
·
·
·
·
·
·
int binary_search(int arr[], int n, int key){ int left = 0, right = n - 1; int mid; while(left <= right){ mid = left + (right - left) / 2; if (arr[mid] >= key) right = mid - 1; else left = mid +1; } if(left < n)return left; return -1; }
【05】给定一个升序的数组，查找最后一个等于key的下标，找不到返归-1。例如：在数组{1,2,2,3,4}中查找2，返回2。请改正错误的地方：
·
·
·
·
·
·
·
·
·
·
·
·
·
·
int binary_search(int arr[], int n, int key){ int left = 0, right = n - 1; int mid; while(left <= right){ mid = left + (right - left) / 2; if (arr[mid] >= key) right = mid - 1; else left = mid +1; } if(right >=0 && arr[right] == key)return right; return -1; }
【06】给定一个升序的数组，查找第一个大于等于key的下标，找不到返归-1。例如：在数组{1,4,5,8,10,10,12,13,15}中查找6，返回3。请改正错误的地方：
·
·
·
·
·
·
·
·
·
·
·
·
·
·
int binary_search(int arr[], int n, int key){ int left = 0, right = n - 1; int mid; while(left <= right){ mid = left + (right - left) / 2; if (arr[mid] > key) right = mid - 1; else left = mid +1; } if(left < n)return left; return -1; }
【07】给定一个升序的数组，查找最后一个小于等于key的下标，找不到返归-1。例如：在数组{1,4,5,8,10,10,12,13,15}中查找11，返回5。请改正错误的地方：
·
·
·
·
·
·
·
·
·
·
·
·
·
·
int binary_search(int arr[], int n, int key){ int left = 0, right = n - 1; int mid; while(left <= right){ mid = left + (right - left) / 2; if (arr[mid] >= key) right = mid - 1; else left = mid +1; } if(right >= 0)return right; return -1; }
【08】二分查找算法的总结，请改正错误的地方：
实际应用中的优化——将判断相等的步骤放到算法末尾。虽然将平均迭代次数增加1，但是每次迭代中的比较次数减少了1次。代码中 left＋（right- left）／2 和（left＋right）／2的结果相同，但是有效防 止了 left 和 right 太大，直接相加导致整数溢出的情况。难点——很多错误程序在面对边界值的时候无法运行，或返回错误结果。时间复杂度——O(n)。空间复杂度——使用递归时是O(n)，使用循环时是O(1)。二分法的应用包括——快速排序、归并排序、二叉搜索树等。
【09】下面是STL标准库的二分函数的描述，改正错误的地方：
STL中的二分函数包括：lower＿bound()，upper＿bound()， binary＿search()。需要包含头文件 #include<algorithm>。要保证数组是有序的，或者先排序。时间复杂度为 O(logn)。在数组 a[n] 中查找 val，用法：返回第一个大于等于val 的元素下标——int pos = lower_bound(a, a+ n,val)返回第一个大于 val的元素下标——int pos = upper_bound(a,a+ n, val)返回是否搜索到 val——bool flag = binary_search(a,a+n,val)。【10】说一说下面代码的输出，然后运行验证：
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
#include<iostream>#include<algorithm>using namespace std;
int main(){ int a[] = {1,2,3,3,3,7,10}; cout << binary_search(a, a + 7, 2) << endl; cout << (lower_bound(a, a + 7, 3) - a ) << endl; cout << (lower_bound(a, a + 7, 12) - a ) << endl; cout << (upper_bound(a, a + 7, 4) - a ) << endl; cout << (upper_bound(a, a + 7, 12) - a ) << endl; return 0;}
【11】说一说下面代码的输出，然后运行验证：
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
#include<iostream>#include<algorithm>using namespace std;
int main(){ int a[] = {10,7,3,3,3,2,2}; cout << binary_search(a, a + 7, 2, greater<int>()) << endl; cout << (lower_bound(a, a + 7, 3, greater<int>()) - a ) << endl; cout << (lower_bound(a, a + 7, 1, greater<int>()) - a ) << endl; cout << (upper_bound(a, a + 7, 4, greater<int>()) - a ) << endl; cout << (upper_bound(a, a + 7, 2, greater<int>()) - a ) << endl; return 0;}
【12】编程题：差等于K的数对
【13】下面是“二分答案”的描述，如果有错误，请改正：有一类问题，并不是要求在一个有序序列中查找某个目标值，而是：问题的解存在于一个有限的范围内，理论上在这个范围内一个个值枚举，最终能找到解。这时需要根据一个判定条件来判定当前枚举值是否最优解。这个范围很大，如果使用暴力枚举则非常耗时。假如这个范围内的数据也是单调的，则可以利用二分查找来一步步的逼近最优解。这个做法也就是二分答案。单调：可以定性描述在一个指定区间内，函数值变化与自变量变化的关系。当函数f（x）的自变量x在其定义区间内增大（或减小）时，函数值f（x）也随着增大（或减小），则称该函数为在该区间上具有单调性（单调递增或单调递减）。【14】编程题：木材加工
【15】编程题：分巧克力
【16】下面“实数二分”的描述，如果有错误，请改正：
当二分查找的区间是一个实数域时，称之为实数二分。实数二分的算法思想没有变化，但是因为实数和整数不同，整数是离散的，可以逐一枚举，区间中除了首尾边界外，每个整数都有一个前驱和一个后继；实数是连续的，所以实现方式和整数二分有所不同。常见的形式是通过确定好精度 prec（如1e-6、1e-8等），以 left＋prec＜right 为循 环条件，然后每次根据在 mid上的判定，选择左半区间［left，mid］ 或右半区间 ［mid，right］。循环结束后，left 即为最终答案。另外一种形式是预估精度，采用限定次数的循环来实现。
代码示例框架如下：
·
·
·
·
·
·
while(left + 1e-6 < right){ double mid = (left + right) / 2; if(check(mid)) left = mid + 1; else right = mid - 1;}
【17】编程题：一元三次方程求解
【17】二分法总结，如果有错误，请改正：二分法的前提条件是，数组／序列必须有序。数组的二分性：以某个下标为分界线，下标左边都匹配某个规则，下标右边都不匹配这个规则。或者下标左边都不匹配某个规则，下标右边都匹配这个规则。当暴力枚举无法完成时，可考虑判定问题是否适合采用二分法来完成，如果可以采用二分法，将会极大的降低时间复杂度。