二分法,以优秀的复杂()度成功的将顺序查找抛在后面,成为我们最常用的算法。
在我们平常的认知里,二分法只能用于解决有序的数据问题,但对于求解内容的不同,它也可以用于无数的数据中,下面就有序数据和无序数据的相关问题进行总结。
1. 二分法解决有序问题
1.1 查找某个数
1.2 大于等于某数最左侧的位置
2. 二分法解决无序问题
2.1 局部最小值问题
首先来解释一下什么是局部最小值:
- 如果这个数在0位置:这个数小于1位置上的数;
- 如果这个数在N位置:这个数小于N-1位置上的数;
- 如果这个数在其他位置:这个数小于前一个位置上的数,还小于后一位位置上的数。
如果在一个无序数组中,相邻两数不相等,则从0 ~ (N-1)上存在局部最小值