Question

二分法思路总结

Answer 1

二分的思想的挺简单的，一开始觉得要考虑很多边界情况。但其实不然，考虑这些边界情况并不会改善算法的时间复杂度。

深刻体会，对于计算机来说，少计算一次两次有什么区别呢。真正影响到执行时间的是内部if，else语句的出口。以及时间复杂度，是一种数量级的增长，而不是一次两次。
如果一定要用if else，那么看是否能用？：表达式代替。

首先二分法的思想
它是一种分治的思想。适用于相对有序的数组。初始化指针在数组的开头和结尾，然后得到中间数，进行比较，移动头尾指针，进行一半的取舍。

普通版的二分查找
给出 arr=[1,2,3,4,5,7,9,11,34,35,44] ，找到数组中是否存在7，找到则并返回下标，找不到则返回-1

进阶版二分查找
例题：给出非递减排序数组的部分翻转数组，找出其最小元素

为什么使用二分
给出的条件是一个相对有序的数组并且因为当数据量大的时候，遍历整个数组，极不友好。也不够高级。

当找到的mid>left，则最小数一定在mid的右侧，当mid<left，最小数一定在mid的左侧（或者是mid）。最后我们会遍历到一个单调增的区域，这个时候直接拿left的值即可，不需要在进行二分了。

事件复杂度：O(lgn)
空间复杂度：O(1)

这个算法很巧妙的避开了[1,1,0,1,1,1]类似这种找到mid（1）和left（1）相同的局面。算法中直接left++，再进行一次计算。

算法好难啊啊
继续加油吧！