在非递减数组nums中，lower_bound(nums, target)返回第一个大于等于target的值得位置，如果nums中元素均小于target（即不存在>=target的元素），则返回nums的长度（即target如果要插入到nums中，应该插入的位置）
#coding=utf-8 #返回nums中第一个>=target的值得位置，如果nums中都比target小，则返回len(nums) def lower_bound(nums, target): low, high = 0, len(nums)-1 pos = len(nums) while low<high: mid = (low+high)/2 if nums[mid] < target: low = mid+1 else:#>= high = mid #pos = high if nums[low]>=target: pos = low return pos
测试：
nums = [10, 10, 10, 20, 20, 20, 30, 30] print lower_bound(nums, 9), print lower_bound(nums, 10), print lower_bound(nums, 15), print lower_bound(nums, 20), print lower_bound(nums, 25), print lower_bound(nums, 30), print lower_bound(nums, 40)
运行结果：
在非递减数组nums中，upper_bound(nums, target)返回第一个大于target的值的位置，如果nums中元素均小于等于target（即不存在>target的元素），则返回nums的长度（即target如果要插入到nums中，应该插入的位置）
#返回nums中第一个>target的值得位置，如果nums中都不比target大，则返回len(nums) def upper_bound(nums, target): low, high = 0, len(nums)-1 pos = len(nums) while low<high: mid=(low+high)/2 if nums[mid]<=target: low = mid+1 else:#> high = mid pos = high if nums[low]>target: pos = low return pos
测试：
nums = [10, 10, 10, 20, 20, 20, 30, 30] print upper_bound(nums, 9), print upper_bound(nums, 10), print upper_bound(nums, 15), print upper_bound(nums, 20), print upper_bound(nums, 25), print upper_bound(nums, 30), print upper_bound(nums, 40)
运行结果：
c++ lower_bound源码参考：http://www.cplusplus.com/reference/algorithm/lower_bound/
c++ upper_bound源码参考：http://www.cplusplus.com/reference/algorithm/upper_bound/
