704. Binary Search

二分法的边界问题还是有一点点搞的，特别是题目变形的时候会发现其实是在猜边界写题....这样其实很不好，我觉得这个边界问题其实就是除法取下界的锅。给出两种错掉的迭代写法：

• 错误写法一:

def bs(a, tar):
    l, r = 0, len(a) - 1
    # while l <= r:                 # <-- wrong: infinite loop
    while l < r: 
        m = (l + r) / 2
        print "bs:  ", m, a[m], l, r
        if a[m] == tar: return m
        if a[m] < tar: l = m + 1 
        if a[m] > tar: r = m 
        # if a[m] < tar: l = m      # <-- wrong: infinite loop
        # if a[m] > tar: r = m - 1
    return -1                       # <-- wrong: cannot find the boundary value

• 这里是l=m+1而不是l=m：是因为除法取下界会造成l边界不会改变，从而形成死循环。

• while l<=r和r=m同时写会造成死循环，例如bs([3,4,7,9,10,11],6)，所以要在l=r的时候跳出循环进行边界检查。这个程序会错的原因是返回时没有进行检查。

• 错误写法二:

def bs1(a, tar):
    l, r = 0, len(a) - 1
    while l < r:                    # <-- wrong: cannot find the boundary value
        m = (l + r) / 2
        print "bs1: " ,m, a[m], l, r
        if a[m] == tar: return m
        if a[m] < tar: l = m + 1
        if a[m] > tar: r = m - 1
    return -1

• l<r没有对边界进行检查。如bs1([3,4,7,9,10,11],11)返回-1

正确写法一：小于判断加检查边界后返回(len(num); l < r; mid)

def bs(nums, target):
    l, r = 0, len(nums) - 1
    while l < r: 
        m = (l + r) / 2
        if nums[m] == target: return m
        if nums[m] < target: l = m + 1 
        if nums[m] > target: r = m 
    if nums[l] == target:  ###### check the boundary 
        return l
    else:
        return -1

变种写法..len(nums) - 1改成len(nums)免去检查

def bs(nums, target):
    l, r = 0, len(nums)
    while l < r: 
        m = (l + r) / 2
        if nums[m] == target: return m
        if nums[m] < target: l = m + 1 
        if nums[m] > target: r = m 
    return -1

一样的java递归写法:

public int search(int[] nums, int target) {
    int l = 0, r = nums.length;
    return dfs(nums, l, r, target);
}

public int dfs(int[] nums, int l, int r, int target) {
    if (l >= r) {
        return -1;
    }
    int m = l + (r - l) / 2;
    if (nums[m] == target) return m;
    if (nums[m] > target) {
        return dfs(nums, l, m, target);
    } else {
        return dfs(nums, m + 1, r, target);
    }
}

正确写法二：小于等于加直接返回(len(num) - 1; l <= r; mid - 1)

def bs(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r: 
        m = (l + r) / 2
        if nums[m] == target: return m
        if nums[m] < target: l = m + 1
        if nums[m] > target: r = m - 1
    return -1

一样的java递归写法:

public int search(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    return dfs(nums, l, r, target);
}

public int dfs(int[] nums, int l, int r, int target) {
    if (l > r) {
        return -1;
    }
    int m = l + (r - l) / 2;
    if (nums[m] == target) return m;
    if (nums[m] > target) {
        return dfs(nums, l, m - 1, target);
    } else {
        return dfs(nums, m + 1, r, target);
    }
}

溢出：

已知 x>l>=0， x>h>=0， h+l>x，由其中的h<x和-l<0得h-l<x，所以h-l不会溢出，又因为l<x，所以l+(h-l)/2不会溢出。

注意java中的优先级，如果不小心写成这样子要在里面加上括号l + ((r - l) >>> 1)

求区间中重复数字的上下界长度：

def lower_bound(a, tar): 
    l, r = 0, len(a)
    while l < r:
        m = l + (r - l) / 2
        if a[m] < tar: 
            l = m + 1
        else: 
            r = m
    return l 

def upper_bound(a, tar): #lower bound
    l, r = 0, len(a)
    while l < r:
        m = l + (r - l) / 2
        if a[m] <= tar: 
            l = m + 1
        else: 
            r = m
    return l 

a=[1, 2, 2, 2, 4, 4, 5]
print lower_bound(a, 2) # 1
print lower_bound(a, 3) # not exist
print upper_bound(a, 2) # 4
print upper_bound(a, 5) # not exist

求下界中，这个条件a[m] < tar的意思是说数组中如果一个数等于target的时候，右边指针会多走一步到达下界。同样在求上界中，a[m] <= tar是说左边指针会多走一步到达上界。