二分查找（floor and ceil）
import math
def floor(arr, target):
'''
在有序数组arr中, 查找target
如果找到target, 返回第一个target相应的索引index
如果没有找到target, 返回比target小的最大值相应的索引, 如果这个最大值有多个, 返回最大索引
如果这个target比整个数组的最小元素值还要小, 则不存在这个target的floor值, 返回-1
'''
left = -1
right = len(arr) - 1
while left = target:
right = mid - 1
else:
left = mid
# 如果该索引+1就是target本身, 该索引+1即为返回值
if left+1 < len(arr) and arr[left+1] == target:
return left + 1
# 否则, 该索引即为返回值
return left
# left = 0
# right = len(arr) - 1
# while left = target:
# right = mid - 1
# else:
# left = mid
# if arr[left] == target:
# return left #
# elif left target:
# return -1
# else:
# return left
def ceil(arr, target):
'''
二分查找法, 在有序数组arr中, 查找target
如果找到target, 返回最后一个target相应的索引index
如果没有找到target, 返回比target大的最小值相应的索引, 如果这个最小值有多个, 返回最小的索引
如果这个target比整个数组的最大元素值还要大, 则不存在这个target的ceil值, 返回整个数组元素个数n
'''
left, right = 0, len(arr)-1
while left < right:
mid = left + (right - left) // 2
if arr[mid] = 0 and arr[right-1] == target:
return right - 1
# 否则, 该索引即为返回值
return right
arr = [1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 5, 5, 5, 6, 6, 6]
print(floor(arr, 2)) # output: 3
print(ceil(arr, 2)) # output: 7
print(floor(arr, 3)) # output: 7
print(ceil(arr, 3)) # output: 8
作者：柯南道尔的春天
