二分查找及原理
程序员文章站
2024-03-19 22:02:16
...
二分查找总是遗漏的点是,二分 运用的是序号,并不是具体的值作为移动。因为使用二分的前提一般就是排好序的,所以,所以,序号的移动也等同于值的移动。
另外一个点,判断输出的条件是,min<max,并且,这样是一定可以输出目标值的,因为边界限制的条件就可以驱使最终到达该值。
二分查找,如果存在的话必定能找到。
def binary_search(list1, target):
left = 0
right = len(list1) - 1
while left <= right:
mid = (left + right) // 2
if list[mid] == target:
return mid
if list[mid] > target:
right = mid
else:
left = mid + 1
return 0
list1 = [1,2,3,4,5,6,7,8,9]
print(binary_search(list1, 9))
下面是一个二分的原理的抽象
- 有序矩阵中第K小的元素
给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。
请注意,它是排序后的第 k 小元素,而不是第 k 个不同的元素。
matrix = [ [ 1, 5, 9],[10, 11, 13],[12, 13, 15]]
k = 8,返回 13。
下面使用的方法是利用了上述数组的特性,从右下角开始,如果该位置小于mid,则可以认为该列的此位置上方的数字都是小于mid,全部加上,并且继续往右走;如果该位置大于mid,则往上走,寻找比它小的。
最后计算上述的加法得到的数目与第k个数的比较!如果比k小,那么认为mid可以加大,所以min = mid + 1,max照旧, mid = (max + min)//2;否则max = mid.
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
def com(matrix, k, mid):
i = len(matrix) - 1
j = 0
num = 0
while i >= 0 and j < len(matrix[0]):
if matrix[i][j] <= mid:
j += 1
num += i + 1
else:
i -= 1
return num >= k
mins = matrix[0][0]
maxs = matrix[-1][-1]
while mins < maxs: ###不要等于号,等于或大于的时候直接输出就行了。
# 加上等于号的话,下面会无线循环 maxs = mid
# 即使找到已经满足k的,但是还继续进行。将其包揽在内,然后无限缩小范围,
mid = (mins + maxs)//2
if com(matrix, k, mid):
maxs = mid
else:
mins = mid + 1
return mins
上一篇: 欧几里得算法求最大公约数及其非公式化证明
下一篇: 求解线性回归方程