25期代码随想录算法训练营第一天 | 704. 二分查找，27. 移除元素

704. 二分查找

链接

代码

左闭右闭 – [left, right]

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)-1

        while l <= r:
            mid = l + (r - l) // 2 #C++ 里面防止溢出，python中没这个考虑
            if nums[mid] < target:
                l = mid + 1
            elif nums[mid] > target:
                r = mid - 1
            else:
                return mid
                
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14

左闭右开 – [left, right)
因为取值取不到nums[r]，所以我们有l < r和r = mid的改动。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)

        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] < target:
                l = mid + 1
            elif nums[mid] > target:
                r = mid
            else:
                return mid
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13

27. 移除元素

链接

代码

双指针

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        l, r = 0, len(nums) - 1 
        while l <= r:
            if nums[l] == val:
                nums[l] = nums[r]
                r -= 1
            else:
                l += 1
        
        return l
1
2
3
4
5
6
7
8
9
10
11

二分题练习

875. 爱吃香蕉的珂珂

链接

代码

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l, r = 1, max(piles)
        res = r
        while l <= r:
            speed = l + (r - l) // 2
            total_time = 0
            for p in piles:
                total_time += math.ceil(float(p) / speed)

            if total_time <= h:
                res = speed
                r = speed - 1
            else:
                l = speed + 1
        
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17