字符串修剪性能对比：while循环实现与二分查找实现孰优孰劣

二分查找是否能提升平均场景下的修剪效率 #

大部分常规业务场景下不能，反而会比传统遍历方案效率更低：

• 传统遍历的时间复杂度为O(x)，x为待修剪的字符数量，常规场景中x通常极小（比如字符串开头的空白多为1~3个），常数成本极低
• 二分查找的时间复杂度固定为O(logn)，每次判断都需要计算中间位、做字符比较，常数成本远高于单步遍历，只有当x远大于log₂n时，二分才有性能优势
• 以长度为100万的字符串为例，log₂n约等于20，也就是说只有当待修剪的字符数超过20个时，二分的运行速度才会超过遍历，这种场景在常规业务中非常少见

基于待修剪字符数x的时间分析 #

二分查找的运行次数仅和字符串总长度n相关，和x无关，时间复杂度恒定为O(logn)，不会因为x的大小出现波动。
两种方案的性能交叉点为x ≈ log₂n：

• x < log₂n时，传统遍历更快
• x > log₂n时，二分查找更快
  如果你的业务场景中大部分待修剪字符串的x都大于log₂n，可以考虑用二分优化，否则优先用传统遍历方案。

你提供的左修剪代码逻辑存在缺陷，无法正常运行 #

存在的问题如下：

• 核心参数缺失：函数没有传入trimChar作为参数，判断逻辑没有依据
• 边界判断错误：当区间长度为2时，仅判断中间位置的字符，无法覆盖区间内两个字符的所有组合情况，比如左字符是待修剪字符、右字符不是的场景，会返回错误值
• 区间计算错误：递归时的中间位计算没有统一使用当前区间的起止位置推导，i/2的写法会直接跳出当前查找区间，导致逻辑混乱
• 返回值逻辑错误：全字符串都是待修剪字符时返回-1不符合预期，应该返回字符串长度；递归调用后没有return语句，无法拿到正确的返回结果
• 功能定位模糊：返回值是最后一个待修剪字符的位置还是第一个非修剪字符的位置没有明确，和最终修剪需要的起始位置不匹配

修正后的二分左修剪参考实现（迭代版，避免递归栈溢出问题） #

def get_left_trim_pos(s: str, trim_char: str) -> int:
    left = 0
    right = len(s)
    while left < right:
        mid = (left + right) // 2
        if s[mid] == trim_char:
            # 中间是待修剪字符，第一个非修剪字符在右侧
            left = mid + 1
        else:
            # 中间不是待修剪字符，第一个非修剪字符在左侧
            right = mid
    return left

# 使用示例：修剪后的字符串为 s[get_left_trim_pos(s, ' '):]

内容的提问来源于stack exchange，提问作者Fly