Implementation and Testing of Exponential Search for scenario where we search the same array/list many times

Question

Exponential Search is an optimization over binary search.

Conceptually, when searching for a number target in a list of numbers nums, exponential search first finds into which power-of-two sized bucket nums[2**p: 2**(p+1)] the target falls into. E.g., if nums has a size of 30, then the buckets are nums[0:1], nums[1:2], nums[2:4], nums[4:8], nums[8:16], and nums[16:30]. After finding an appropriate bucket, say nums[lo:hi], then we do a standard binary search for target, but we limit our scope of search to just nums[lo:hi].

Here's my implementation of Exponential Search for a scenario where we want to search multiple/many targets within the same list of numbers:

from bisect import bisect_left, bisect_right

INF = float('inf')

class ExpSearch:
    def __init__(self, nums, max_target=None):
        self.N = len(nums)
        self.nums = nums
        self.max_target = INF if max_target is None else max_target
        self.pows = []
        self.part = []
        i = 1
        while i < self.N and nums[i] <= self.max_target:
            self.pows.append(i)
            self.part.append(nums[i])
            i <<= 1
        # (i == 1 and self.N <= 1 or nums[1] > self.max_target) or
        #   (i//2 < self.N and self.part[-1] == nums[i//2] <= self.max_target)
        # i >= self.N or nums[i] > self.max_target
        if i < self.N:
            self.pows.append(i)
            self.part.append(nums[i])
        self.P = len(self.part) # == len(self.pows)
        self.pows.append(self.N) # Force self.pows(self.P) == self.N
        self.pows.append(0) # Force self.pows[-1] == 0
        # (i >= self.N and self.part[-1] == nums[1 << (self.P - 1)] <= self.max_target) or
        #   (i < self.N and self.part[-1] == nums[1 << (self.P - 1)] > self.max_target)

    def find_left(self, target, lo=0, hi=None):
        assert target <= self.max_target
        hi = self.N if hi is None else hi
        p = bisect_left(self.part, target)
        # self.part[:p] < target
        # self.part[p:] >= target
        # p == 0 or self.part[p-1] == self.nums[1 << (p-1)] < target
        # p == self.P or self.part[p] == self.nums[1 << p] >= target
        
        # lo = max(lo, 1 << (p-1) if p > 0 else 0)
        # hi = min(hi, 1 << p if p < self.P else self.N)

        lo = max(lo, self.pows[p-1])
        hi = min(hi, self.pows[p])
        return bisect_left(self.nums, target, lo, hi)

    def find_right(self, target, lo=0, hi=None):
        assert target <= self.max_target
        hi = self.N if hi is None else hi
        p = bisect_right(self.part, target)
        # self.part[:p] <= target
        # self.part[:p] > target
        # p == 0 or self.part[p-1] == self.nums[1 << (p-1)] <= target
        # p == self.P or self.part[p] == self.nums[1 << p] > target
        
        # lo = max(lo, 1 << (p-1) if p > 0 else 0)
        # hi = min(hi, 1 << p if p < self.P else self.N)
        
        lo = max(lo, self.pows[p-1])
        hi = min(hi, self.pows[p])
        return bisect_right(self.nums, target, lo, hi)

Here's the code with fewer comments:

from bisect import bisect_left, bisect_right

INF = float('inf')

class ExpSearch:
    def __init__(self, nums, max_target=None):
        self.N = len(nums)
        self.nums = nums
        self.max_target = INF if max_target is None else max_target
        self.pows = []
        self.part = []
        i = 1
        while i < self.N and nums[i] <= self.max_target:
            self.pows.append(i)
            self.part.append(nums[i])
            i <<= 1
        if i < self.N:
            self.pows.append(i)
            self.part.append(nums[i])
        self.P = len(self.part) # == len(self.pows)
        self.pows.append(self.N) # Force self.pows(self.P) == self.N
        self.pows.append(0) # Force self.pows[-1] == 0

    def find_left(self, target, lo=0, hi=None):
        assert target <= self.max_target
        hi = self.N if hi is None else hi
        p = bisect_left(self.part, target)
        lo = max(lo, self.pows[p-1])
        hi = min(hi, self.pows[p])
        return bisect_left(self.nums, target, lo, hi)

    def find_right(self, target, lo=0, hi=None):
        assert target <= self.max_target
        hi = self.N if hi is None else hi
        p = bisect_right(self.part, target)
        lo = max(lo, self.pows[p-1])
        hi = min(hi, self.pows[p])
        return bisect_right(self.nums, target, lo, hi)

1. Any suggestions/improvements are welcome!
2. Can you think of a better name for self.part?
3. I use self.pows == [1 << p for p in range(self.P)] so that instead of doing 1 << p, I can just do self.pows[p]. Actually, self.pows == [1 << p for p in range(self.P)] + [self.N, 0]. The [self.N, 0] tail simplifies the lo = max(lo, ...) and hi = min(hi, ...) code.
4. A lot of the code is invariants (conditions that hold at that point of execution) as comments. Is there a better way to convey these invariants/conditions?

---

I also wrote some test code. My main priority is to get a code review on the implementation, but I would be glad to hear suggestions/comments about the test code as well.

from random import randint
from .expsearch import ExpSearch

N = 1_000 # 100_000
MIN = -10_000
MAX = 10_000
T = 100

def gen_nums(N, min_, max_):
    return [randint(min_, max_) for _ in range(N)]

def test():
    nums = gen_nums(N, MIN, MAX)
    nums.sort()
    ES = ExpSearch(nums)
    for _ in range(T):
        target = randint(MIN-0.1*abs(MIN), MAX+0.1*abs(MAX))
        l = ES.find_left(target)
        # assert all(num < target for num in nums[:l])
        # assert all(num >= target for num in nums[l:])
        assert l == 0 or nums[l-1] < target
        assert l == N or nums[l] >= target

        r = ES.find_right(target)
        # assert all(num <= target for num in nums[:r])
        # assert all(num > target for num in nums[r:])
        assert r == 0 or nums[r-1] <= target
        assert r == N or nums[r] > target
        
        print(f"Passed with target = {target}")

The test code generates a sorted list of size N whose values lie within [MIN, MAX] == [-10_000, 10_000] inclusive. Then it runs T = 100 tests. In each test, a random target is generated. The random target is:

• within [MIN, MAX] with chance greater than 80%,
• below MIN with a >8% chance, and
• above MAX with a >8% chance.

Then the test tries to find target within nums using both ExpSearch.find_left and ExpSearch.find_right. In each case, the test checks that the returned index is correct.

I ran the tests with two N's.

• N = 1_000 produces a sparse nums since N == 1_000 << MAX - MIN == 20_000. It is unlikely that the generated nums has a lot of duplicates.
• N = 100_000 produces a dense nums since N == 100_000 >> MAX - MIN == 20_000. It is guaranteed that the generated nums has duplicates (in fact, it has at least 80_000 duplicates).

All tests pass.

Answer 1

(Exponential Search is an improvement over binary search
where the target can be expected to be close to some starting point.)

• class ExpSearch does not have a documented purpose and scope of application.
  Same applies to find_left() and find_right()
• using binary search on the pre-determined "partition values" it does not implement exponential search:
  The probing sequence is much different.
  It should be conventional using part.index(target), instead - if lo was 0:
• if lo != 0, the values in part aren't helpful in finding bounds for binary search
• I think the "invariant comments" great.
• The test doesn't exercise setting no and hi

Minor:
• P isn't really used
• using __init__(self, nums, max_target=INF) allows self.max_target = max_target

It would be great if the test compared measures of effort for binary & exponential search for uniform, binomial and exponential distribution.