不同路径II
leetcode每日一题-通配符匹配
leetcode每日一题-最长有效括号
二分查找算法总结
二分查找算法总结
二分查找思路很简单，从一个有序数组中对某个目标数进行折半查找，不断缩小范围，直到找到这个数。但二分查找实现的细节却有很多，很多时候不注意，结果就会很玄学。
基本模板如下：
1 | int binarySearch(int[] nums, int target){ |
2 | int left=0, right=...; |
3 | while(...){ |
4 | // mid=(left+right)/2相加结果有可能会溢出 |
5 | // 这里的left+(right-left)/2就可以避免这种情况 |
6 | int mid = left + (right-left)/2; |
7 | if(nums[mid] == target){ |
8 | ... |
9 | }else if(nums[mid] < target){ |
10 | left = ... |
11 | }else if(nums[mid] > target){ |
12 | right = ... |
13 | } |
14 | } |
15 | return ...; |
16 | } |
其中...标记的地方，就是可能出现细节问题的地方。我们分别考虑二分查找的三种情况，分别是寻找一个数（基本的二分搜索）、寻找左侧边界的二分搜索以及寻找右侧边界的二分搜索。
