二分查找的三种写法：

  1. 正常写法，返回正好等于那个数的位置： 

    1
    2
    3
    4
    5
    6
    7
    8
    def bisect_normal(a, x):  
    	l, h = 0, len(a) - 1
    	while l <= h:
    		m = (l + h) // 2
    		if x == a[m]: return m
    		elif x > a[m]: l = m + 1
    		else: h = m - 1
    	return -1

  2. 返回大于等于x的第一个位置

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    def bisect_left(a, x, lo=0, hi=None):
        if lo < 0:
            raise ValueError('lo must be non-negative')
        if hi is None:
            hi = len(a)
        while lo < hi:
            mid = (lo+hi)//2
            if a[mid] < x: lo = mid+1
            else: hi = mid
        return lo

  3. 返回大于x的第一个位置

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    def bisect_right(a, x, lo=0, hi=None):
        if lo < 0:
            raise ValueError('lo must be non-negative')
        if hi is None:
            hi = len(a)
        while lo < hi:
            mid = (lo+hi)//2
            if x < a[mid]: hi = mid
            else: lo = mid+1
        return lo

注意：m = ( l + h) // 2 会溢出 （虽然python不会），建议采用 m = l + (h - l) // 2