二分查找是一个很经典和常用的查找算法，作用在一个有序序列中。其基本思想是 “夹逼”或者“排除”。
查找元素位置
https://leetcode-cn.com/problems/search-insert-position/
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。 示例 1: 输入: [1,3,5,6], 5 输出: 2
示例 2: 输入: [1,3,5,6], 2 输出: 1
示例 3: 输入: [1,3,5,6], 7 输出: 4
示例 4: 输入: [1,3,5,6], 0 输出: 0
这个问题是在传统二分法问题上增加了查找目标值不存在的情况下，按序插入的位置。
解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def find_position(nums: list, target: int):
if not nums:
# 空的，返回首位
return 0
left = 0 # 第一位
right = len(nums) - 1 # 最后一位
while left < right:
mid = (left + right) // 2 # 中间一位
if target < nums[mid]: # 目标值比中间值小，往左收缩范围
right = mid
elif target > nums[mid]: # 目标值比中间值大，往右收缩范围
left = mid + 1 # 目标值一定是大于中间值的数
else: # 正好找到，返回
return mid
return left # 没有找到，要插入的位置即是 left
if __name__ == '__main__':
data = [1, 3, 5, 6, 7, 9, 12]
print(find_position(nums=data, target=3)) # 1
print(find_position(nums=data, target=10)) # 6
print(find_position(nums=[], target=10)) # 0
上面的解法也可以修改为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def find_position(nums: list, target: int):
if not nums:
return 0
left = 0
right = len(nums) # 若 target 比 nums 中的所有元素都大时，应该返回最后一个元素索引+1，即 len(nums)
while left < right:
mid = (left + right) >> 1 # 整除2
if target > nums[mid]: # 目标值大于 mid 的话，往右缩小范围
left = mid + 1
else: # 否则往左缩小范围
right = mid
return left
if __name__ == '__main__':
data = [1, 3, 5, 6, 7, 9, 12]
print(find_position(nums=data, target=3)) # 1
print(find_position(nums=data, target=10)) # 6
print(find_position(nums=[], target=10)) # 0
求平方根
https://leetcode-cn.com/problems/sqrtx/
实现 int sqrt(int x) 函数。 计算并返回 x 的平方根，其中 x 是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。 示例 1: 输入: 4 输出: 2
示例 2: 输入: 8 输出: 2
说明: 8 的平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。
解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def cal_floor_sqrt(num):
if num < 0:
return
left = 0
right = num
while left < right:
mid = (left + right + 1) >> 1
if mid ** 2 > num:
right = mid - 1 # 结果小于 mid，往左缩小范围
else:
left = mid # 结果大于等于mid，往右缩小范围
return left
if __name__ == '__main__':
print(cal_floor_sqrt(1)) # 1
print(cal_floor_sqrt(2)) # 1
print(cal_floor_sqrt(3)) # 1
print(cal_floor_sqrt(4)) # 2
print(cal_floor_sqrt(5)) # 2