人菜还要学算法

二分法

#!/usr/bin/python
# -*- coding: utf-8 -*-
from functools import wraps
from random import randrange


class Dichotomy:
    def __init__(self, arr, target, not_then_return):
        self.arr = arr
        self.target = target
        self.not_then_return = not_then_return

    def __dichotomy(self):
        left, right = 0, len(self.arr) - 1
        ret = None
        while left <= right:
            m = (left + right) // 2
            if self.comp(self.arr[m], self.target):
                ret = m
                right = m - 1
            else:
                left = m + 1
        return ret

    def wrap_solve(self, func):
        @wraps(func)
        def wrapper(*args, **kwargs):
            _id = self.__dichotomy()
            return func(_id, self.arr, self.not_then_return, *args, **kwargs) if _id                 else self.not_then_return
        return wrapper

    def __call__(self, func_comp, func_solve, *args, **kwargs):
        self.comp = func_comp
        return self.wrap_solve(func_solve)(*args, **kwargs)


if __name__ == ‘__main__‘:
    arr = sorted([randrange(50) for i in range(20)])
    target = 233
    not_then_return = float(‘-inf‘)
    print(Dichotomy(arr=arr, target=target, not_then_return=not_then_return)(
            func_comp=lambda i, _target: i**2 > _target,
            func_solve=lambda i, _arr, n_t_r: (i, _arr[i]) if i != n_t_r else n_t_r))

つづく

人菜还要学算法

原文：https://www.cnblogs.com/jsoneri/p/14984358.html