承接上文 插入排序和二分法
局部最小值问题
在数组中 无序 任何2个相邻的数不相等 局部最小定义 如果0位置上的数小于1位置上的数 那么0位置就是局部最小的位置 如果N-1位置上的数 小于 N-2位置上的数 那么N-1就是局部最小位置 如果中间位置i即比左边i-1位置小同时也比i+1位置小 那么i位置就是局部最小 i位置必须同时小于左边和右边的数 才叫局部最小 在这样一个数组中 找出一个局部最小即可 能不能求的过程 时间复杂度好于O(N) 最好二分 ？
解题
先看0位置是不是局部最小 如果0位置是局部最小 就直接返回了 如果0位置不是局部最小 那就是比1位置大 那么在0～1之间是向下的趋势
在看下N-1位置 如果N-1位置是局部最小 如果N-1位置是局部最小 就直接返回了 如果不是 则在N-2 ~ N-1 这个范围上是向下的趋势
0位置到N-1位置必存在局部最小 因为相邻两个数不相等就一定存在整个数组上值的变化波动曲线 直接取中点位置M
如果M位置上的数比M-1位置上的数要小 比M+1位置上的数还要小 这个M就是局部最小值 如果M比M-1位置上的数要大
那么在M-1 ～ M之间是向下的趋势 那么0-M范围必存在局部最小
什么时候适合二分
日常定出一个流程 优化方向就2个方向 1)数据状况 2)问题标准（这个题是局部最小标准） 这个题是2个结合起来 这种数据状况下求解这个问题就存在二分策略 当构建一个排他性的问题 比如左边有 右边没有 就可以使用二分了
对数器
有一个想要测的方法a 同一个问题可能有很多中策略来实现 如果不管时间复杂度好坏的话 可以写出一个暴力尝试的写法（一个题把所有的排列组合都弄一遍） 但做题的时候有时间限制可能一些方法不过 把这样的不追求时间复杂度优劣 但很好想 很好写的方法叫方法b 比如刚才那个二分的问题 可以用二分的方法找局部最小 也可以用遍历的方式找局部最小 通过线上oj(测试平台)方法进行测试 可能存在没有oj或者测试用例不全（可能存在 没有代码跑出错 也测试通过的情况） 即想测的方法a即使通过了线上oj也不能保证一定正确 这就有了对数器的方法 这是万无一失的方法 生成一个随机样本发生器 可以产生随机样本 在方法a跑一遍 得到结果a 在方法b跑一遍 得到结果b 比如测试几千万次 当发现两个结果不一样 要么方法a错了 要么方法b错了 要么两个方法都错 给一个小样本 比如长度为5的数组 通过人看的方式看看方法a结果和方法b的结果 就可以知道方法a、方法b是否对错 用人工干预的方式把方法a和方法b都修改对 然后把随机样本产生数的长度设置大些，值也更随机些 跑个几千万次 就可以确定方法a对了 这个就比线上oj平台更加可靠了
准备一个方法b
测试50万次 每一次都会生成一个随机数组（长度也随机、值也随机）
Math.random() 表示在[0,1)所有小数 等概率返回一个 这个在数学上是做不到的 在计算机是可以的 因为0-1范围的所有小数在计算机是有穷尽的 精度更好的小数认为不存在了 Math.random() * N 返回[0,N)上的所有小数 等概率返回一个 （int）(Math.random() * N) 转换成整数 就会在[0,N-1]所有整数 等概率返回一个 利用这个机制实现数组长度的随机 对应上图中的第一行代码 for循环里面是2个随机数相减得到的结果也是随机的
继续分析主方法
每一次都会生成一个随机数组 范围是0～100 值范围是-100~100 得到arr1 然后把arr1拷贝出来一份arr2 让想测的方法a去排序arr1 再用对数器方法（方法b）去排序arr2 isEqual方法表示是否每个位置上的值都一样 一样 true,不一样false 如果有不一样的 则随机范围调小一点 人工干预的方式看看2个排序方法哪个排错了 然后去调试 再跑对数器 直接每一次结果都一样 这种方法需要写2个方法（两套独立思路写出来的东西） 但非常稳 不依赖线上测试平台
