首页 > 代码库 > 第二节.二分法
第二节.二分法
总结：
1什么时候使用二分法？
当要求使用比O（n）还要低的时间复杂度时，只能是O（lgn）。通常对应二分法和倍增法。
2二分法模板：
首先看一个经典的二分查找问题：
在一个排序数组中找一个数，返回该数出现的任意位置，如果不存在，返回-1
样例
给出数组 [1, 2, 2, 4, 5, 5].
- 对于 target =
2, 返回 1 或者 2. - 对于 target =
5, 返回 4 或者 5. - 对于 target =
6, 返回 -1.
代码：
public class Solution { public int findPosition(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int start = 0, end = nums.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (nums[mid] <= target) { start = mid; } else { end = mid; } } if (nums[start] == target) { return start; } if (nums[end] == target) { return end; } return -1; }}
上面模板中需要注意：
1.while循环条件 start+1<end 可以保证循环内start和end不相邻，从而避免死循环。
2.mid = start+(end-start)/2 可以防止溢出。
3.每次的更新要使用 start = mid 或 end = mid。
4.前面的while循环目的是缩小查找区间，直到start和end相邻，因此while里面可以不return。
5.熟练此模板，对于其他的二分查找问题，只需要根据题意改变缩小区间的条件即可。
第二节.二分法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。