欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分查找及原理

程序员文章站 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))

下面是一个二分的原理的抽象

  1. 有序矩阵中第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

相关标签: 剑指offer