二分法图解（二分法是怎么用的）

语言学里面的层次分析法和框式图解法有什么区别？

以下是一个以框式图解法分析句子的一例子:

在婆娑的树影下,一对白天鹅正在闲适地游戈。

└—————┘ └———————————┘

状语 主谓

└————┘└—————┘

主语 谓语

└—┘└—┘└——┘└——┘

定语 中心语 状语 中心语

由大到小的分析。

层次分析法刚好与他相反，是由小到大的分析

算法图解1-2/11

原书作者 Aditya Bhargava

二分法查找，正是猜数字游戏的玩法：A从1-100中随机挑一个数，B来猜，A返回B猜的数是大了还是小了，最快的一种方法就是二分法（猜50--小了，接下来猜75……）

不同的算法，运行时间差异很大。

五种最常见的算法运行时间

数组就是一列相邻的数据，位置关系固定，查找(读取很快)，要插入1个数据时，必需把后面的数据全部移动一位；但如果内存中的连续空位不够时就比较麻烦；

链表中中每个元素会记录下一个元素的位置，所以插入很好操作——只需修改一个指向记录。删除操作类似的，也只需要更改某下一个元素的指向位置即可。

选择排序：遍历这个列表，找出播放次数最多的乐队，并将该乐队添加到一个新列表中。接下来继续该操作(找到第二多的乐队)，最终得到一个有序列表。

每次操作需要针对剩余的n个元素(n,n-1,……1，平均为n 1/2)，共操作n次，故算法时间为O(n n*1/2)，通常忽略常数项，得算法时间为O(n^2)

X^2=2^x这种方程怎么解？

可以把等式两边作为函数画图像求解，函数图像交点的横坐标就是对应的解，这个题可以代数进去测试，大于0的解有2和4，需要注意指数函数的增长速度快于幂函数，此外还有一个小于0的解，不能直接给出，但通过代数测试和函数图像交点可以大概给出其范围。

二分法图解

二分法的宗旨，在于每次搜索的时候舍弃了解不在的那一半，最后将区间缩小并逼近解。不仅是全集有序可以使用，分段有序也可以使用。

二分法算法框架

我们知道两个数的中位数，可以使用Δx/2 + x，也可以(x1+x2)/2；但是出于极端的考虑，x1+x2有可能出现Integer或者long越位，所以推荐使用Δx/2 + x。

给定一个有序数组的任意次右移结果，找出某个元素的位置，不存在返回-1。

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2])。

在确定分段有序的时候，如果target在此范围内，就缩小到此范围，否则就使用另外一半区间。

这是上一题有duplicate的升级。

在一个旋转数组中找出最小值。

2,2,2,0,1为例

（1）找到中间位置，中间位置[2]没有[1]大，则start区间前进到mid，此时start=2,end=4

（2）找到中间位置，中间位置[0]比[1]要小，则end缩短至mid，此时start=2,end=3

（3）结束，比较2，3位置取最小值

如果mid位置等于end位置，则end直接往前移动一个位置。