BinarySelection

Complexity

Total Complexity

7

Size/Duplication

Total Lines	21
Duplicated Lines	0 %

Importance

Changes	2
Bugs	1	Features	0

1 Method

Rating	Name	Duplication	Size	Complexity
B	index_of()	0	20	7

from pyalgs.algorithms.commons.util import is_sorted, less


class BinarySelection(object):
    @staticmethod
    def index_of(a, x, lo=None, hi=None):
        if not is_sorted(a):
            raise ValueError('array must be sorted before running selection')

        if lo is None:
            lo = 0
        if hi is None:
            hi = len(a) - 1

        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if less(x, a[mid]):
                hi = mid - 1
            elif less(a[mid], x):
                lo = mid + 1
            else:
                return mid

        return -1