Binary Search

看了一篇对二分查找总结的非常好的文章，以前也没想过二分法中有这么多门道

二分法的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int l = 0;
int r = nums.size(); //
while(l <= r)  //
{
    int mid = (l+r)/2;
    if(nums[mid] == target)
    {
        //
    }
    else if(nums[mid] > target)
    {
        //
    }
    else if(nums[mid] < target)
    {
        //
    }
}

加注释的地方都是依据不同情况来定的，比如根据查找区间

• 如果区间是 [ left ， right ]，r在初始化时就需要为num.size() - 1，while中的条件为l <= r
• 如果区间是 [ left ， right )，r在初始化时就需要为num.size()，while中的条件为l < r

而且根据查找要求，判断后语句也不一样

• 可以直接返回mid
• 可以使right = mid-1，也可以使right = mid

等

详文 二分法详解