二分查找

• 二分查找的各种写法以及对应边界

搜索区间为闭区间[i,j]
关于的取值，需要覆盖整个搜索区间。
关于返回值，根据实际情况确定。
比如，在精准查找某个元素时，我们可以写成如下的代码：

def search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            l = mid + 1
        else:
            r = mid - 1
    return -1

而如果是在一个没有重复元素的数组里查询目标值，查询不到返回顺序插入的位置，代码则应该写成

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l , r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return l

搜索区间为开区间[i,j)
两种更新方式

可以参考基础练习的leftBound和rightBound两个函数的实现来加深理解。这样的更新方式是为了防止死循环。

• python库函数的使用

导入：from bisect import *
参数形式：有序列表，目标值

• 基础练习
  • 返回在有序数组中插入目标值的位置，如果数组中存在相同值，返回最左侧下标。(对应python中bisect库的bisect_left)

返回值的范围在。表示数组的长度。返回0时表示，插入的元素比最小值还小，或者相等。返回时表示插入的元素比最大值还大。

 def bisect_left(nums, target):  # 自己的实现
     l, r = 0, len(nums)
    while l < r:
        mid = (l + r) // 2
        if nums[mid] < target:
            l = mid + 1
        else:
            r = mid
    return l

• 返回在有序数组中插入目标值的位置，如果数组中存在相同值，返回最右侧下标。(对应python中bisect库的bisect_right)

返回值的范围在。表示数组的长度。返回0时表示，插入的元素比最小值还小，返回时表示插入的元素比最大值还大或者相等。

 def bisect_right(nums, target):
     l, r = 0, len(nums)
    while l < r:
        mid = (l + r) // 2
        if nums[mid] <= target:
            l = mid + 1
        else:
            r = mid
    return l

• 返回在有序数组中目标元素第一次出现的位置。不存在则返回-1。循环结束后还需要对边界值进行特殊判断。

  def leftBound(nums, target):
    l, r = 0, len(nums) - 1
  while l < r:
     mid = (l + r) // 2
     if nums[mid] < target:
         l = mid + 1
     else:
         r = mid
  return l if nums[l] == target else -1

• 返回在有序数组中目标元素最后一次出现的位置。不存在则返回-1。循环结束后还需要对边界值进行特殊判断。

  def rightBound(nums, target):
  l, r = 0, len(nums) - 1
  while l < r:
     mid = (l + r + 1) // 2
     if nums[mid] <= target:
         l = mid 
     else:
         r = mid - 1
  return l if nums[l] == target else -1
  

• 利用二分查找搜索边界点

我们称一个分割整数数组的方案是 好的 ，当它满足：
数组被分成三个 非空 连续子数组，从左至右分别命名为 left ， mid ， right 。
left 中元素和小于等于 mid 中元素和，mid 中元素和小于等于 right 中元素和。
给你一个 非负 整数数组 nums ，请你返回 好的 分割 nums 方案数目。由于答案可能会很大，请你将结果对取余后返回。
题目来源：LeetCode
题目链接：https://leetcode-cn.com/problems/ways-to-split-array-into-three-subarrays
数据规模：
3 <= nums.length <= 10
0 <= nums[i] <= 10
分析：
数据规模决定了采用时间复杂度为的算法。
首先需要构造前缀和数组，前缀和数组定义为。因为数组中元素均为非负数，所以前缀和数组不严格单增。
设两个切分点为，满足
所以思路是枚举所有的，寻找满足条件的并且计数。
固定，寻找第一个满足条件的，使得。
移项，寻找最后一个满足条件的，使得。
参考解答：

class Solution:
    def waysToSplit(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        n = len(nums)
        pre = list(accumulate(nums))  # 前缀和数组，不含有前导0 from itertools import accumulate
        ans = 0
        for i in range(n):
            l = max(i+1, bisect_left(pre, pre[i]*2)) # 找到大于等于目标值的下标，相同元素返回最左下标
            r = min(n-1, bisect_right(pre, (pre[i]+pre[-1])//2)) # 若寻找到的数恰好等于目标值，返回最右下标；若大于目标值，返回当前下标
            ans += max(0, r - l) # j的可行区间为[l, r)
        return ans % mod  #  python可以最后再取余