暴力做法：遍历每个数，询问他是否 ≥ target？

时间复杂度：O(n)

二分做法：

要求 nums 是非递减的，即 nums[i] <= nums[i + 1]

返回第一个大于等于 target 的 i，如果不存在，返回 len(nums)

如果 target 在 M 右边，那么将 L 更新到 M + 1

其他语言直接相加可能会溢出，可改为 mid = left + (right - left) // 2

# 左右闭区间写法
def b_s(nums, target):
    left = 0
    right = len(nums) - 1 # 区间 [left, right]
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return left # right + 1

# 左闭右开区间写法
def b_s2(nums, target):
    left = 0
    right = len(nums) # 区间 [left, right)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left # right

# 左右开区间写法
def b_s3(nums, target):
    left = -1
    right = len(nums) # 区间 (left, right)
    while left + 1 < right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid
        else:
            right = mid
    return left + 1 # right

nums = [5,7,7,8,8,10], target = 8

上面是 ≥ target 写法，记为 ≥ x

如果是 > target，可以转换为 ≥ x + 1，使用 b_s(nums, target + 1)

如果是 < target，可以转换为 (≥ x) - 1，使用 b_s(nums, target) - 1

如果是 ≤ target，可以转换为 (> x) - 1，使用 b_s(nums, target + 1) - 1

时间复杂度：O(logn)

空间复杂度：O(1)

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

   class Solution:
   def searchRange(self, nums: List[int], target: int) -> List[int]:
       def b_s(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
   
       start = b_s(nums, target)
       end = b_s(nums, target + 1) - 1
       if len(nums) == 0 or start > end:
           return [-1, -1]
       return [start, end]

   时间复杂度：O(logn)

   空间复杂度：O(1)

2. 35. 搜索插入位置

   class Solution:
   def searchInsert(self, nums: List[int], target: int) -> int:
       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

   时间复杂度：O(logn)

   空间复杂度：O(1)

3. 704. 二分查找

   class Solution:
   def search(self, nums: List[int], target: int) -> int:
       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 -1 if left == len(nums) or nums[left] != target else left

   时间复杂度：O(logn)

   空间复杂度：O(1)

4. 744. 寻找比目标字母大的最小字母

   class Solution:
   def nextGreatestLetter(self, letters: List[str], target: str) -> str:
       target = chr(ord(target) + 1)
       left = 0
       right = len(letters) - 1
       while left <= right:
           mid = (left + right) // 2
           if letters[mid] < target:
               left = mid + 1
           else:
               right = mid - 1
       return letters[0] if left == len(letters) else letters[left]

   时间复杂度：O(logn)

   空间复杂度：O(1)

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

   class Solution:
   def maximumCount(self, nums: List[int]) -> int:
       def b_s(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
   
       neg = b_s(nums, 0)
       pos = len(nums) - b_s(nums, 1)
       return max(neg, pos)

   时间复杂度：O(logn)

   空间复杂度：O(1)

   才知道可以 from bisect import bisect_left ，直接调用 bisect_left 求第一个 ≥ target， bisect_right 求第一个 > target 的，一直都是手搓二分┭┮﹏┭┮

   class Solution:
   def maximumCount(self, nums: List[int]) -> int:
       neg = bisect_left(nums, 0)
       pos = len(nums) - bisect_right(nums, 0)
       return max(neg, pos)

   时间复杂度：O(logn)

   空间复杂度：O(1)

6. 1385. 两个数组间的距离值

   class Solution:
   def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
       arr2.sort()
       res = 0
       for x in arr1:
           left = bisect_left(arr2, x - d)
           right = bisect_left(arr2, x + d)
           if left == right:
               if left < len(arr2):
                   if arr2[left] != x + d and arr2[left] != x - d:
                       res += 1
               else:
                   res += 1
       return res

   时间复杂度：O(nlogn)

   空间复杂度：O(1)

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

   class Solution:
   def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
       potions.sort()
       res = []
       for sp in spells:
           if success // sp == success / sp:
               res.append(len(potions) - bisect_left(potions, success // sp))
           else:
               res.append(len(potions) - bisect_right(potions, success // sp))
       return res

   时间复杂度：O((n+m)logm)，其中 n 为 spells 的长度，m 为 potions 的长度。排序 O(mlogm)。二分 n 次，每次 O(logm)。

   空间复杂度：O(n)

8. 2389. 和有限的最长子序列

   class Solution:
   def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
       nums.sort()
       res = []
       for q in queries:
           left = 0
           right = len(nums) - 1
           while left <= right:
               mid = (left + right) // 2
               if sum(nums[:mid + 1]) <= q:
                   left = mid + 1
               else:
                   right = mid - 1
           res.append(left)
       return res

   时间复杂度：O((n+m)logn)，其中 n 为 nums 的长度，m 为 queries 的长度。排序为 O(nlogn)，m 次二分查找为 O(mlogn)。

   空间复杂度：O(n)

   灵神用了一个前缀和，可以直接使用 bisect ，简单了非常多！你是我的神！

   class Solution:
   def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
       nums.sort()
       res = []
       for i in range(1, len(nums)):
           nums[i] += nums[i - 1]
       for x in queries:
           res.append(bisect_right(nums, x))
       return res

   时间复杂度：O((n+m)logn)，其中 n 为 nums 的长度，m 为 queries 的长度。排序为 O(nlogn)，m 次二分查找为 O(mlogn)。

   空间复杂度：O(n)

9. 1170. 比较字符串最小字母出现频次

   纯模拟，感觉写复杂了，倒是能过

   class Solution:
   def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
   
       def f(s):
           min_c = 'z'
           cnt = 0
           for c in s:
               if c < min_c:
                   min_c = c
                   cnt = 1
               elif c == min_c:
                   cnt += 1
           return cnt
   
       for i, w in enumerate(words): # m
           words[i] = f(w) # L_avg
       words.sort() # mlogm
       res = []
       for q in queries: # n
           target = f(q) # L_avg
           res.append(len(words) - bisect_right(words, target)) # logm
       return res

   时间复杂度：O(m * L_avg + m log m + n * (L_q + log m))，m 是单词列表 words 的大小。n 是查询列表 queries 的大小。L_avg 是单词的平均长度。L_q 是查询的平均长度。

   空间复杂度：O(n)