【基础算法精讲-学习记录】二分查找1

视频学习记录

https://www.bilibili.com/video/BV1AP41137w7

• 二分查找遵循两个不变量原则，分别是左指针以左不符合和右指针以右符合（具体是否包括左右指针自身根据取的闭区间或者开区间决定）

• 判断左右指针更新后是否为mid或者加减一，也是看区间，如果是闭区间，那么左右指针一开始就是可能的边界值，那么最后一个值时，两个指针是同一个位置，自然需要加减一，否则死循环。

• 熟悉后，对于问题的二分可以倒着推导。比如题目要求找到一个数值h，这个h需要在满足某些条件下尽量大或者尽量小，那么就假设找到题目说的h，看看h的左右两侧是不是符合某些性质，比如左边都不符合条件，右侧都符合这种。然后根据这些信息就可以确定左右指针怎么更新等二分细节。

例题和课后作业代码记录

34. 在排序数组中查找元素的第一个和最后一个位置

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

def lowerBound(nums, target):
        left = 0
        right = len(nums)-1 # 闭区间

        while left <= right:
            mid = (left + right) // 2 # 向下取整
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid -1 

        return left # 或者right+1，保持left左边小于target，right右边大于等于target

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # 时间复杂度logn 空间 1
        start = lowerBound(nums, target)
        if start == len(nums) or nums[start] != target:# 第一个排除数组都是空，或者数组都小于target，第二个排除数组中没有target
            return [-1, -1]
        end = lowerBound(nums, target+1) - 1 # 前面确认过数组非空且有target，所以这里不用再检验
        return [start, end]

2529. 正整数和负整数的最大计数

https://leetcode.cn/problems/maximum-count-of-positive-integer-and-negative-integer/description/

def lowerBound(nums, target):
    left = 0
    right = len(nums)-1 # 闭区间

    while left <= right:
        mid = (left + right) // 2 # 向下取整
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid -1 

    return left # 或者right+1，保持left左边小于target，right右边大于等于target

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        n = len(nums)
        neg_end = lowerBound(nums, 0)
        # if neg_end == n:
        #     return neg_end
        pos_start = lowerBound(nums, 1)
        # if pos_start == -1:
        #     return n
        # print(pos_start, " ", neg_end)
        return max(neg_end, n-pos_start)

        

2300. 咒语和药水的成功对数

https://leetcode.cn/problems/successful-pairs-of-spells-and-potions/description/

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        # 时间复杂度O（len(postions)*log(len(postions)) + len(spells)*log(potions))空间复杂度O1（不考虑排序内部和答案
        ans = []
        n = len(potions)
        potions.sort()
        for spell in spells:
            cur_success = 0
            fail_cnt = bisect_left(potions, success/spell)
            success_cnt = n - fail_cnt
            ans.append(success_cnt)
        return ans

1385. 两个数组间的距离值

https://leetcode.cn/problems/find-the-distance-value-between-two-arrays/description/

class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        # 时间nlogn，主要是排序；空间1
        arr2.sort()
        
        # 让1的元素a在2中没有周围d以内的，可以转化为找a-2和a+2在arr2的所属位置，如果能找到范围内数字就不符合距离要求
        ans = 0
        for a in arr1:
            # 这是直接排除最极端的情况，加速
            if a+d < arr2[0] or a-d > arr2[-1]:
                ans += 1
                continue
            target_low_idx = bisect_left(arr2, a-d)
            # 第一种情况是极端情况，虽然排除了，但还是先写着
            # 第二种就是大于等于a-d的第一个元素在【a-d，a+d】这个区间中，就不符合距离要求了，不需要另一个坐标
            if target_low_idx < len(arr2) and arr2[target_low_idx] > a + d:
                ans += 1
        return ans
            

2080. 区间内查询数字的频率

https://leetcode.cn/problems/range-frequency-queries/description/

class RangeFreqQuery:
    # 暴力思路是取区间然后逐一遍历，这种方法的空间O1，不需要额外空间，但是时间需要On
    # 如果改进，应该是对于数组虽然按数值排序，但是同时保留对应的下标
    # 查找时直接找有几个值，然后看这些值的下标是否符合，这样的空间n，但是时间logn
    def __init__(self, arr: List[int]):
        self.rec = defaultdict(list)
        for i, x in enumerate(arr):
            self.rec[x].append(i)

    # 注意是闭区间
    def query(self, left: int, right: int, value: int) -> int:
        start = bisect_left(self.rec[value], left)
        end = bisect_right(self.rec[value], right)
        return end - start
        

# Your RangeFreqQuery object will be instantiated and called as such:
# obj = RangeFreqQuery(arr)
# param_1 = obj.query(left,right,value)

2563. 统计公平数对的数目

https://leetcode.cn/problems/count-the-number-of-fair-pairs/description/

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums.sort()
        # 除了On方的暴力，大致有两种，要么对相同元素计数，要么直接二分找到对应的下标差
        # 但由于滑动窗口下，窗口没有单调性指引缩小，所以不适合对相同元素计数这步
        # 时间nlogn，主要是排序，空间1
        ans = 0
        for i, x in enumerate(nums):
            start = bisect_left(nums, lower-x, 0, i)
            end = bisect_right(nums, upper-x, 0, i)
            ans += end-start
        return ans

875. 爱吃香蕉的珂珂

https://leetcode.cn/problems/koko-eating-bananas/description/

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # 二分估计，最坏的情况是按照堆中最大的数值，可以向下二分地猜
        # 空间O1，时间复杂度logn
        l = 1
        r = max(piles)

        while l <= r:
            mid = (l+r) // 2
            if sum([(pile+mid-1) // mid for pile in piles]) > h:
                l = mid + 1
            else:
                r = mid - 1


        return l

2187. 完成旅途的最少时间

https://leetcode.cn/problems/minimum-time-to-complete-trips/description/

class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        # 时间log n，空间 1
        # 这里用的是闭区间
        max_time = max(time)
        l = 1
        r = max_time * totalTrips
        n = len(time)
        while l <= r:
            mid = (l+r) // 2
            curTrips = sum([mid // time[i] for i in range(n)])
            if curTrips >= totalTrips: # 这里的 = 重要，只有这样才会在trips数相同时取小
                r = mid - 1
            else:
                l = mid + 1

        return l

275. H 指数 II

https://leetcode.cn/problems/h-index-ii/description/

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        # 暴力做法是从高往低遍历，求已遍历数字长度和当前数字值取小值
        # 想要对数时间复杂度，就需要二分取数字长度
        n = len(citations)
        l = 0
        r = n
        while l <= r:
            mid = (l+r) // 2
            # if n-mid <= citations[mid]: # 说明从这往右的都满足大于自己的位置长度（末尾起算）
            #     r = mid-1
            # else:
            #     l = mid+1
            if citations[-mid] >= mid: # 右边mid篇文章至少有mid引用
                l = mid+1
            else:
                r = mid-1
        
        return r
            

2439. 最小化数组中的最大值

https://leetcode.cn/problems/minimize-maximum-of-array/description/

class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        # 假定存在数字h符合题目的最小的那个最大值，那么可以设置一个数字去逼近h
        # 时间logn，空间 1
        l = 0
        r = max(nums)
        n = len(nums)
        while l <= r:
            mid = (l+r)//2
            
            cur = 0
            for i in range(n-1, -1, -1):
                cur = max(0, cur+(nums[i]-mid))
            
            if cur > 0: # 不满足条件，需要增大这个最大值的量
                l = mid+1
            else:
                r= mid-1
        
        return l