学习笔记

1. 讲到深度遍历的时候，遍历一颗树，会先从root节点开始遍历，然后遍历root的左孩子，左孩子的左孩子，左孩子的左孩子的左孩子…… 如果遍历的深度足够深的话，会不会很容易产生栈溢出错误（Java的话，就是StackOverFlowError）？如果容易产生的话，要怎么规避呢？

使用二分查找，寻找一个半有序数组 [4, 5, 6, 7, 0, 1, 2] 中间无序的地方

思路：

1. 半有序数组，总体而言是单调递增的，只是中间被打断换了方向，也有上下界，数组可以通过下标访问，因此可以使用二分查找。

2. 可以强行使用二分查找，每次循环，首先获得左右边界值left，right、中间值mid，如果总元素个数为奇数，将原数组分成[0, mid-1]和[mid]，[mid+1, right]三个数组。如果为偶数，分成[0,mid]和[mid+1, right]两个数组。

3. 两个子数组，分别进行如下处理：

a. 如果当前数组的元素个数大于3，分成两个子数组。

b. 如果当前数组的元素个数等于3（左中右三个元素），比较左中右的大小关系，如果满足左>中，或者中>右，则分界点就是左中或者中右。如果满足左<中<右的关系，返回另一个子数组进行前述的比较。

c. 如果当前数组的元素个数等于2，如果该数组的元素满足k-1 > k的关系，则返回该结果，否则进入另一个子数组进行比较，如果两个子数组均不满足，则比较左数组的k和右数组的k-1，如果满足左数组的k>右数组的k-1的关系，则返回该结果，否则返回上一级进行比较。

感觉这个思路还要包括分治递归在里面了，想不清楚了……