the following signatures couldn't be verified because the public key is not available: NO_PUBKEY 3B4FE6ACC0B21F32





This error occurs when trying to install or update a package in Ubuntu or Debian that requires an authentication key which is not present on your system. To resolve the issue, you can import the missing public key using the following command:
```python
sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys 3B4FE6ACC0B21F32
```

This will fetch and add the missing key to your system's trusted keys list. After that, you should be able to install or update the package without any further issues.

following signatures couldn‘t be verified because the public key is not available: NO_PUBKEY

# 介绍





贪心算法是一种基于贪心思想的算法，它每次选择当前最优的解决方案，从而得到全局最优解。具体来说，贪心算法在每一步都做出局部最优选择，希望通过这种方式最终达到全局最优解。贪心算法通常适用于问题具有最优子结构性质和无后效性的情况。尽管贪心算法并不总是能够得到最优解，但它通常具有高效、简单等优点，并且在许多实际问题中得到了广泛应用。

一般来说，可以从以下几个方面考虑如何区别题目要使用贪心算法还是动态规划算法：

1、问题的性质：贪心算法适用于具有最优子结构性质和无后效性的问题，而动态规划算法则适用于具有重叠子问题和最优子结构性质的问题。

2、对时间复杂度的要求：贪心算法通常比动态规划算法更加高效，但并不总能得到最优解。如果对时间复杂度有较高的要求，可以首先考虑贪心算法；否则可以使用动态规划算法。

3、解决问题的方式：贪心算法通常是从局部最优解推导出全局最优解，即每次都选择当前最优解，并期望通过这种方式得到最终的最优解。而动态规划算法则是通过将问题分解成多个子问题，并保存已经求解过的子问题的结果，然后再利用这些子问题的结果求解更大的子问题，最终得到全局最优解。

4、是否存在贪心选择性质或者无后效性质：关键在于是否能够证明问题具有贪心选择性质或者无后效性质，如果问题确实具有这些性质，那么使用贪心算法也许是一个较好的选择。





![在这里插入图片描述](/static/img/images/04626.png)



# 分配饼干

[https://leetcode.cn/problems/assign-cookies/description/](https://leetcode.cn/problems/assign-cookies/description/)

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

```python
class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        i, j = 0, 0
        while i < len(g) and j < len(s):
            if g[i] <= s[j]:
                i += 1
            j += 1
        return i
```

# K 次取反后最大化的数组和

[https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/](https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/)

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

```python
class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort()
        for i in range(len(nums)):
            if nums[i] < 0 and k > 0:
                nums[i] = -nums[i]
                k -= 1
            else:
                break
        nums.sort()
        if k % 2 == 1:
            nums[0] = -nums[0]
        return sum(nums)
```

# 柠檬水找零

[https://leetcode.cn/problems/lemonade-change/](https://leetcode.cn/problems/lemonade-change/)

使用贪心算法解决该问题，具体步骤如下：

1、初始化变量 fives, tens 为 0，分别表示手中拥有的 5 元和 10 元数量。

2、对于每个顾客支付的钞票金额 bill，进行如下操作：

- 如果 bill 为 5 元，则不需要找零，直接将手中的 5 元数量加 1。

- 如果 bill 为 10 元，则需要找零 5 元，此时需要检查手中是否有足够的 5 元可找零，如果没有则返回 False；否则将手中的 10 元数量加 1，将手中的 5 元数量减 1。

- 如果 bill 为 20 元，则需要找零 15 元，优先使用一张 10 元和一张 5 元找零，如果手中没有足够的 10 元和 5 元，则尝试使用三张 5 元找零，如果还是无法找零，则返回 False。

 

3、如果成功为所有顾客找到了零钱，则返回 True。

```python
class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        fives = tens = 0
        for bill in bills:
            if bill == 5:
                fives += 1
            elif bill == 10:
                if not fives:
                    return False
                fives -= 1
                tens += 1
            else:
                if tens and fives:
                    tens -= 1
                    fives -= 1
                elif fives >= 3:
                    fives -= 3
                else:
                    return False
        return True
```



# 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。


```python
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return len(nums)
        up = down = 1
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                up = down + 1
            elif nums[i] < nums[i-1]:
                down = up + 1
        return max(up, down)
```

# 单调递增的数字

[https://leetcode.cn/problems/monotone-increasing-digits/](https://leetcode.cn/problems/monotone-increasing-digits/)

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

```python
class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        s = str(n)
        i = 1
        while i < len(s) and s[i - 1] <= s[i]:
            i += 1
        if i < len(s):
            while i > 0 and s[i - 1] > s[i]:
                s = s[:i - 1] + str(int(s[i - 1]) - 1) + '9' * (len(s) - i)
                i -= 1
        return int(s)
```

# 买卖股票的最佳时机 II

[https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/)

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

 

在贪心策略中，前一天价格低就买入，然后在今天卖出。
```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        profit = 0
        for i in range(1,len(prices)):
            if prices[i] > prices[i-1]:
                profit+=(prices[i]-prices[i-1])
        return profit
```

# 买卖股票的最佳时机含手续费

[https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/)

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

```python
class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        if not prices:
            return 0
        profit = 0
        buy_price = prices[0]
        for i in range(1, len(prices)):
            # 如果当前价格比之前买入价加手续费高，就可以卖出股票并获得利润
            if prices[i] >= buy_price + fee:
                profit += prices[i] - (buy_price + fee)
                buy_price = prices[i] - fee  # 更新买入价为当前价减去手续费
            # 如果当前价格比之前买入价便宜，就考虑更新买入价
            elif prices[i] < buy_price:
                buy_price = prices[i]
        return profit
```

# 分发糖果

[https://leetcode.cn/problems/candy/description/](https://leetcode.cn/problems/candy/description/)

```python
class Solution(object):
    def candy(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int 贪心策略，两遍遍历。第一遍右边元素比左遍元素大，则糖果为左边糖果加1.第2遍左边元素比右边元素大，则糖果为右边加1或者或者为本身糖果数量。
        """
        if len(ratings)<2:
            return len(ratings)
        assign=[1 for _ in ratings]
        for i in range(1,len(ratings),1):
            if ratings[i]>ratings[i-1]:
                assign[i]=assign[i-1]+1
        for i in range(len(ratings)-1,0,-1):
            if ratings[i-1]>ratings[i]:
                assign[i-1]=max(assign[i-1],assign[i]+1)
        return sum(assign)
```

# 根据身高重建队列

[https://leetcode.cn/problems/queue-reconstruction-by-height/description/](https://leetcode.cn/problems/queue-reconstruction-by-height/description/)

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

 输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

解释：

编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。

编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。

编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。

编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。

编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。

编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。

因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

```python
class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # 按照身高从高到低排列，如果身高相同则按照前面大于等于身高的人数从小到大排序
        people.sort(key=lambda x: (-x[0], x[1]))
        queue = []
        # 将每个人插入到队列中，位置由前面大于等于身高的人数决定
        for p in people:
            queue.insert(p[1], p)
        return queue
```

# 跳跃游戏

[https://leetcode.cn/problems/jump-game/description/](https://leetcode.cn/problems/jump-game/description/)

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

```python
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        farthest = 0
        for i in range(n):
            if i <= farthest:
                farthest = max(farthest, i + nums[i])
                if farthest >= n - 1:
                    return True
        return False
```

# 跳跃游戏 II

[https://leetcode.cn/problems/jump-game-ii/description/](https://leetcode.cn/problems/jump-game-ii/description/)

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i] 

i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

 
```python
class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0
        max_pos, step, end = 0, 0, 0
        for i in range(n-1):
            max_pos = max(max_pos, i + nums[i])
            if i == end:
                end = max_pos
                step += 1
        return step
```

# 用最少数量的箭引爆气球

[https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/](https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/)

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
```python
class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0
        # 按照气球结束坐标从小到大排序
        points.sort(key=lambda x:x[1])
        # 初始化箭的射出位置为第一个气球的结束坐标
        arrow_pos = points[0][1]
        count = 1
        for i in range(1, len(points)):
            # 如果下一个气球的开始坐标大于当前箭的射出位置，则需要再发射一支箭
            if points[i][0] > arrow_pos:
                arrow_pos = points[i][1]
                count += 1
        return count
```

# 无重叠区间

[https://leetcode.cn/problems/non-overlapping-intervals/submissions/417134877/](https://leetcode.cn/problems/non-overlapping-intervals/submissions/417134877/)

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

 

具体实现过程如下：

首先判断输入是否为空，如果为空则直接返回0。

对输入列表按照每个区间的结束位置进行排序，即按照x[1]排序。

初始化变量end为第一个区间的结束位置，count为1，表示当前至少需要保留一个区间。

遍历排序后的区间列表，若当前区间的开始位置大于等于end，则说明该区间与前一个区间不重叠，将end更新为当前区间的结束位置，同时count加1。

若当前区间的开始位置小于end，则说明该区间与前一个区间重叠，则需要移除其中一个区间。因为已经将区间按照结束位置排序，所以优先保留结束位置更早的区间，因此将end更新为前一个区间的结束位置和当前区间的结束位置中较小的那个。

最终返回需要移除的区间数量，即总区间数减去保留的区间数。
```python
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key=lambda x: x[1])
        end = intervals[0][1]
        count = 1
        for i in range(1, len(intervals)):
            if intervals[i][0] >= end:
                end = intervals[i][1]
                count += 1
            else:
                end = min(end, intervals[i][1])
        return len(intervals) - count
```


# 划分字母区间

[https://leetcode.cn/problems/partition-labels/description/](https://leetcode.cn/problems/partition-labels/description/)

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

 

 遍历字符串，对于每个字符记录它最后一次出现的位置；

维护一个起始位置和结束位置，表示当前片段的范围；

如果当前位置等于结束位置，说明当前位置是一个片段的结束位置，将该片段长度添加到结果数组中，并将起始位置设为结束位置的下一个位置；

最终返回结果数组。

```python
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {c:i for i, c in enumerate(s)}
        start = end = 0
        res = []
        for i, c in enumerate(s):
            end = max(end, last[c])
            if i == end:
                res.append(end - start + 1)
                start = end + 1
        return res
```

【算法题目】【Python】一文刷遍贪心算法题目

难度可以控制，且解法唯一，时间复杂度看运气。







首先，我们定义了一个 SudokuGenerator 类。然后，我们定义了 generate 方法来生成数独游戏。该方法生成了一个 9 × 9 的矩阵，初始值为 '.'。接着，使用 solveSudoku 方法来解决数独游戏，并将解决后的结果存放在生成的矩阵中。

在求解数独游戏时，我们使用深度优先搜索算法来实现。对于每个单元格，首先检查它是否有预设值（即是否为 '.'），如果有，直接跳过。如果没有，我们随机生成1~9的数字，并检查该数字是否符合数独规则，如果不符合规则，就换一个数字再次尝试，直到找到符合规则的数字。将符合规则的数字填入该单元格，并继续向后搜索，直到搜索完成整个数独游戏。

然后，我们定义了 removeNumbers 方法来删除数独游戏，使难度符合所选根据。在此方法中，我们使用深度优先搜索算法来逐步删除数独游戏中的数字。我们找到所有预设数字的单元格，并随机打乱它们的顺序。然后尝试删除单元格中的数字，并确保解法唯一，如果解法唯一，继续删除数字，否则回退上一个状态。

最后，我们定义了 isUnique 和 solve 方法来解决数独游戏。isUnique 方法用于确定给定的游戏是否具有唯一解。该方法使用深度优先搜索算法，在填写数字的过程中判断是否出现多个解决方案。 solve 方法解决数独游戏，将字符串表示为数独板，并返回解决结果的一个布尔值。

```python
import random
class SudokuGenerator:
    def __init__(self, difficulty):
        # 限制在30和60之间
        if difficulty < 30:
            self.difficulty = 30
        elif difficulty > 60:
            self.difficulty = 60
        else:
            self.difficulty = difficulty
    def generate(self):
        board = [['.' for _ in range(9)] for _ in range(9)]
        self.solveSudoku(board)
        self.removeNumbers(board, self.difficulty)
        return board
    def solveSudoku(self, board):
        def dfs(board, row, col):
            if col == 9:
                return dfs(board, row + 1, 0)
            if row == 9:
                return True
            if board[row][col] != '.':
                return dfs(board, row, col + 1)
            nums = list(range(1, 10))
            random.shuffle(nums)
            for i in nums:
                if not isValid(board, row, col, str(i)):
                    continue
                board[row][col] = str(i)
                if dfs(board, row, col + 1):
                    return True
                board[row][col] = '.'
            return False
        def isValid(board, row, col, c):
            for i in range(9):
                if board[i][col] == c:
                    return False
                if board[row][i] == c:
                    return False
                if board[(row // 3) * 3 + i // 3][(col // 3) * 3 + i % 3] == c:
                    return False
            return True
        dfs(board, 0, 0)
    def removeNumbers(self, board, difficulty):
        def dfs(board, num):
            if num == 0:
                return True
            lst = [(i, j) for i in range(9) for j in range(9) if board[i][j] != '.']
            lst = sorted(lst, key=lambda x: random.random())
            for i, j in lst:
                c = board[i][j]
                board[i][j] = '.'
                if not self.isUnique(board):
                    board[i][j] = c
                elif dfs(board, num - 1):
                    return True
                else:
                    board[i][j] = c
            return False
        dfs(board, difficulty)
    def isUnique(self, board):
        s = ''.join([''.join(row) for row in board])
        solver = SudokuSolver()
        return solver.solve(s)
class SudokuSolver:
    def solve(self, s):
        board = [[s[i * 9 + j] for j in range(9)] for i in range(9)]
        return self.solveSudoku(board)
    def solveSudoku(self, board):
        def dfs(board, row, col):
            if col == 9:
                return dfs(board, row + 1, 0)
            if row == 9:
                return True
            if board[row][col] != '.':
                return dfs(board, row, col + 1)
            for i in range(1, 10):
                if not isValid(board, row, col, str(i)):
                    continue
                board[row][col] = str(i)
                if dfs(board, row, col + 1):
                    return True
                board[row][col] = '.'
            return False
        def isValid(board, row, col, c):
            for i in range(9):
                if board[i][col] == c:
                    return False
                if board[row][i] == c:
                    return False
                if board[(row // 3) * 3 + i // 3][(col // 3) * 3 + i % 3] == c:
                    return False
            return True
        return dfs(board, 0, 0)
generator = SudokuGenerator(50)  # 挖空多少个格子
board = generator.generate()
for row in board:
    print(row)
print(str(board).count("."))
```


检查时间复杂度：

```python
import time
ties = []
for _ in range(100):
    t0 = time.time()
    generator = SudokuGenerator(60)  # 挖空多少个格子
    board = generator.generate()
    # for row in board:
    #     print(row)
    ties.append(time.time() - t0)
print(max(ties))
print(min(ties))
print(sum(ties) / len(ties))
```

得到的生成游戏所消耗的时间是：

254.41049194335938

0.02700185775756836

7.814508402347565

最大时间居然需要254秒，需要改进。

【算法题目】使用Python生成一个数独游戏的棋盘

【算法题目】【Python】彻底刷遍DFS与回溯的算法题目

参考：[https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/wo-xie-le--9c7a4/](https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/wo-xie-le--9c7a4/)






#  1 基本介绍

二分查找法（Binary Search）是一种在**有序数组**中查找某一特定元素的搜索算法。其基本思想是，首先将整个有序数列分成前后两部分，判断在哪个部分中可能会找到要查找的数，然后递归地在那个部分中查找。

具体来说，首先选择数列的中间元素。如果要查找的数比中间元素小，则在数列的左半部分继续查找；如果要查找的数比中间元素大，则在数列的右半部分继续查找；如果相等，则找到了要查找的数。这样一直递归进行，直到找到要查找的数或者整个数列被查找完。

二分查找法的时间复杂度为 O(log n)，其中 n 是数列中的元素个数。由于其在有序数列中查找元素的时间复杂度较低，因此常用于大规模有序数列的查找。

> 二分查找并不简单，Knuth 大佬（发明 KMP 算法的那位）都说二分查找：思路很简单，细节是魔鬼。

- 有哪些细节：

> while循环中使用 low <= high 还是 low < high ？ 

> if条件里写<还是<=? 是low = mid +1？

> 还是low = mid ？



# 2 基本的二分查找

基本的二分查找中有序数组里的元素没有重复数值，而二分查找的目的就是找到符合条件的下标。

比如想在有序数组 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] 中找到元素5的index，该如何写python代码呢：

```python
def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:  # 结束条件是 low > high， 为什么不用<符号呢：因为当low=high时，还需要判断一次，不然[low,high]就会被漏掉
        mid = (low + high) // 2  # 和mid=low+(high-low)//2是一样的结果，low+(high-low)//2可以防止大数溢出
        if arr[mid] < x:
            low = mid + 1  # 在区间 [mid+1, high] 中查找
        elif arr[mid] > x:
            high = mid - 1  # 在区间 [low, mid-1] 中查找
        elif arr[mid] == x:
            return mid
    return -1
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
x = 5
result = binary_search(arr, x)
if result != -1:
    print(f"Element is present at index {result}")
else:
    print("Element is not present in array")
```

# 3 左边界 vs 右边界，查找相等的元素

当有序数组中存在重复值，即是由多个元素可以满足条件，返回哪一个下标更合适呢？

比如 arr = [1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9]， 找数值5，那么左边界index是4，右边界index是6。 

如果有序数组中有重复值，并且你想找到左边界的下标，你可以在二分查找的基础上，做一些改变来实现这个功能。

下面的代码展示了左边界和右边界的代码：

```python
def binary_search_leftright(arr, x):
    low = 0
    high = len(arr) - 1
    result = -1
    while low <= high:  # 结束条件是 low > high， 为什么不用<符号呢：因为当low=high时，还需要判断一次，不然[low,high]就会被漏掉
        mid = (low + high) // 2  # 和mid=low+(high-low)//2是一样的结果，low+(high-low)//2可以防止大数溢出
        if arr[mid] < x:
            low = mid + 1  # 在区间 [mid+1, high] 中查找
        elif arr[mid] > x:
            high = mid - 1  # 在区间 [low, mid-1] 中查找
        elif arr[mid] == x:
            result = mid  # 记录符合条件的下标
            # high = mid - 1  # 在区间 [low, mid-1] 中查找，这就很灵性，意味着找到了，但是还要继续找，而且趋势是往左找. 即找左边界。
            low = mid + 1  # 在区间 [mid+1, high] 中查找，这就很灵性，意味着找到了，但是还要继续找，而且趋势是往右找. 即找右边界。
    return result
arr = [1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9]
x = 5
result = binary_search_left(arr, x)
if result != -1:
    print(f"Element is present at index {result}")
else:
    print("Element is not present in array")
```

# 4 难度升级，找到 x<6 的右边界

在 arr = [4, 4, 5, 5, 6, 6, 7, 8, 9] 中找到一个元素x，满足x<6，且x是右边界元素：
```python
def binary_search_right(arr, x):
    low = 0
    high = len(arr) - 1
    while low < high:
        mid = (low + high) // 2
        if arr[mid] < x:
            low = mid + 1  # 继续在[mid+1, high]中查找，因为想找右边界
        else:
            high = mid  # 为什么不是mid-1呢?
    if arr[high] >= x:
        return high - 1
    else:
        return high
arr = [4, 4, 5, 5, 6, 6, 7, 8, 9]
x = 6
result = binary_search_right(arr, x)
print(result)
```

函数返回 high - 1 或者返回high。


- 如果将条件改为while low <= high呢，这样不可以吗？

> 如果你将循环的条件改为 while low <= high，在数组中查找小于目标值的右边界的时候是会有问题的。

> 

> 当low==high时，如果arr[high] >= x 那么最终返回值就是high -1,而实际上并不是小于目标值的右边界。

> 

> 因此，在二分查找中查找右边界时，循环条件应该是 low < high.

> 

> 这样当循环结束时，high指向的就是第一个大于等于目标值的位置，而high - 1就是小于目标值的右边界

> 

> 所以，在二分查找中查找右边界时，循环条件应该是 low < high 而非 low <= high,这是为了确保查找的正确性

> 

> 除此之外，还可能发生死循环。


- 那为什么是high = mid ，而不是high = mid -1？

> 在查找小于目标值的右边界时，如果循环条件是 low < high, 当 arr[mid] >= x 时,如果 high = mid -1 会使得 high 不满足循环条件,从而导致循环终止，而不是移动到小于目标值的右边界。

> 

> 而赋值high = mid会使得high = mid或者 high =

> mid-1,这样high总是满足循环条件且正确地找到了第一个大于等于目标值的位置,而high-1就是小于目标值的右边界。

> 

> 所以如果你想在查找小于目标值的右边界时，应该让 high = mid。这样可以保证查找的正确性。


# 5 找到 x>5 的左边界

在 arr = [4, 4, 5, 5, 6, 6, 7, 8, 9] 中找到一个元素x，满足x>5，且x是左边界元素：

```python
def binary_search_left(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] <= x:
            low = mid + 1
        else:
            high = mid - 1
    return low
arr = [4, 4, 5, 5, 6, 6, 7, 8, 9]
x = 5
result = binary_search_left(arr, x)
print(result)
```

或者：

```python
def binary_search_left(arr, x):
    low = 0
    high = len(arr)
    while low < high:
        mid = (low + high) // 2
        if arr[mid] <= x:
            low = mid + 1
        else:
            high = mid 
    return low
```


# 6 总结模板

当使用 "while low <= high" 时，要想结束循环，就需要更严格的判断，从而就不需要再单独对low 和high 进行特判。

如果要查找左边界（x>5的左边界）：

```python
def binary_search_left(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] <= x: # 如果是x>=5，这里就需要改变查找区间
            low = mid + 1
        else:
            high = mid - 1
    return low
```

如果要查找右边界（x<6的右边界）：

```python
def binary_search_right(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < x: # 如果是x<=6，这里就需要改变查找区间
            low = mid + 1
        else:
            high = mid - 1
    return high
```

介绍

参考资料