binary_search

python工具！！！

import bisect

使用见

https://codeforces.com/contest/1971/problem/E

1.经典版本：

def binary_search(arr, target):

    l, r = 0, len(arr) - 1

   

    while l <= r:

        mid = l + r >> 1

        if arr[mid] < target:

            l = mid + 1

        elif arr[mid] > target:

            r = mid - 1

        else:

            return mid

    return -1

重复查找第一个

def binary_search_frist(arr, target):

    l, r = 0, len(arr) - 1

   

    while l <= r:

        mid = l + r >> 1

        if arr[mid] == target:

            if mid == 0 or arr[mid - 1] != target:

                return mid

            else:

                r = mid - 1

        elif arr[mid] > target:

            r = mid - 1

        else:

            l = mid + 1

    return -1

重复查找最后一个

def binary_search_last_occurrence(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + right >> 1
        if arr[mid] == target:
            if mid == len(arr) - 1 or arr[mid + 1] != target:
                return mid
            else:
                left = mid + 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

2.小数点二分：

小数点二分不能使用 >>1 会导致出错

在Python中，`>>` 是位移操作符，用于将一个二进制数向右移动指定的位数。如果应用于一个整数，它会将整数向右移动指定的位数，相当于除以2的指定次幂，然后向下取整。但是，如果应用于一个小数，它会将小数转换为整数再进行移位操作。
例如，对于小数点 `0.5`，其二进制表示为 `0.1`。将其向右移动一位，即 `0.1 >> 1`，结果为 `0`。因为在二进制中，向右移动一位相当于将原数字除以2。

一般有精确度 向后取一位

代码：1.where 条件 2.由于为小数点忽略加的精度（对于题目而言）

a, b, c, d = list(map(float, input().split()))


def function(x):
    return a * x ** 3 + b * x ** 2 + c * x + d


count = 0
for i in range(-100, 101):
    l = i
    r = i + 1
    f_l, f_r = function(l), function(r)
    if f_l == 0:
        print('%.2f' % l, end = ' ')
        count += 1
    elif f_l * f_r < 0:
        while r - l >= 0.001:
            mid = (l + r) / 2
            if function(mid) * function(l) < 0:
                r = mid
            else:
                l = mid
        print('%.2f' % l, end=' ')
        count += 1
    if count == 3:
        break

3.元素不在列表中：

查找比target 小的 最大 element

l = 0, r = len - 1

while l < r: # end l = r

    mid = l + r + 1 >> 1

    if arr[mid] <= target:

        l = mid

    else:

        r = mid - 1

找比target 大的 最小 element：

l = 0, r = len - 1

while l < r:

    mid = l + r - 1 >> 1

    if arr[mid] >= target:

        r = mid

    else:

        l = mid + 1

关于二分答案：

只需要记住经典版本，外加定义check（函数就可以），因为这里符号条件即可，不是在本质上遍历数组，而是假设答案查找。