欢迎加入QQ讨论群258996829
苹果6袋
麦子学院
Php二分法详解
发布时间：2016-12-21 15:38 回复:0 查看:2364 最后回复：2016-12-21 15:38
在php开发中，二分法应该算是算法里最基本的一种方法了，常用于在一个有序数组中查找某个值第一次出现的位置、最后出现的位置、或者是一段区间。
有序数组中如果用暴力的贪心算法，即遍历，时间复杂度是O(n)。
用二分法后，由于每次可以去掉一半无用的区间，会将时间复杂度减少到O(logn)。
二分法的基本做法是：
1、确定要查找的区间。
2、确定要二分时的参照点。
2、区间内选取二分点。
3、根据二分点的值，综合左右区间情况以及求解的目的，舍去一半无用的区间。
4、在有用的区间继续进行二分搜索。
下面是几道比较经典的题目：
1、给定一个升序数组以及一个目标整数target，返回target首次出现的下标位置，如果不存在返回-1。
此题目已给定升序数组，所以待求区间确定，第一步就可省略了。
2、同样是上面的题目，条件变换一下，即给定的数组可以想想为无穷大，但是你可以通过get_value($key)来获取某个下标下的值，求target第一次出现的位置。
此时相当于给定的区间不确定了，所以你先要锁定一个求解区间，增加代码如下：
3、假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7可能变成是4 5 6 7 0 1 2）。你需要找到其中最小的元素。你可以假设数组中不存在重复的元素。
如上图旋转排序数组有以下两种情况，两种情况下最小元素都是小于数组中最后一个元素的，所以可以把数组最后一个元素的值当做参考点。
来源：公众账号
有序数组中如果用暴力的贪心算法，即遍历，时间复杂度是O(n)。
用二分法后，由于每次可以去掉一半无用的区间，会将时间复杂度减少到O(logn)。
二分法的基本做法是：
1、确定要查找的区间。
2、确定要二分时的参照点。
2、区间内选取二分点。
3、根据二分点的值，综合左右区间情况以及求解的目的，舍去一半无用的区间。
4、在有用的区间继续进行二分搜索。
下面是几道比较经典的题目：
1、给定一个升序数组以及一个目标整数target，返回target首次出现的下标位置，如果不存在返回-1。
此题目已给定升序数组，所以待求区间确定，第一步就可省略了。
2、同样是上面的题目，条件变换一下，即给定的数组可以想想为无穷大，但是你可以通过get_value($key)来获取某个下标下的值，求target第一次出现的位置。
此时相当于给定的区间不确定了，所以你先要锁定一个求解区间，增加代码如下：
3、假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7可能变成是4 5 6 7 0 1 2）。你需要找到其中最小的元素。你可以假设数组中不存在重复的元素。
如上图旋转排序数组有以下两种情况，两种情况下最小元素都是小于数组中最后一个元素的，所以可以把数组最后一个元素的值当做参考点。
来源：公众账号