6
\$\begingroup\$

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.

\$\endgroup\$
6
  • 3
    \$\begingroup\$ Please don't modify your code after receiving answers. This potentially invalidates the answer(s) and is overall confusing for everyone reading this Q & A later. If you have a new version with major improvements, feel free to ask a new, follow up question instead. \$\endgroup\$
    – Mast
    Jun 12 at 5:57
  • 1
    \$\begingroup\$ My review is short as it is because I am looking forward to a (cross-linked) follow-on question with signatures like find_left(self, target, start, offset=0, shift=1):, offset 0 meaning figure out direction yourself, >0 up (and don't bother to look at start), <0 down. And shift is the modification to the skip length. \$\endgroup\$
    – greybeard
    Jun 12 at 7:49
  • \$\begingroup\$ @greybeard Not sure I'm understanding. What direction are you referring to? offset > 0 indicates that nums is sorted in ascending order? Also not sure what is meant by "modification of the skip length". \$\endgroup\$
    – joseville
    Jun 13 at 0:05
  • \$\begingroup\$ You coded one of the modifications mentioned by en.wikipedia, Bentley&Yao Algorithm B_1 (Binary Search), who didn't do more to name any of the algorithms. Just as linear search refers (at least conceptually) to index values increasing by one, I'd use exponential search for a base b to increasing powers - what they call the gambler's strategy. (Base 2^k is convenient where a binary search is to follow.) \$\endgroup\$
    – greybeard
    Jun 13 at 11:25
  • \$\begingroup\$ You hyperlinked this code representation from a question about 2SUM. In that scenario, not only is the promising index to start looking for a complement 0 at most once, but the direction alters between hi&lo. And it is known that the starting index does not indicate the target. \$\endgroup\$
    – greybeard
    Jun 13 at 11:33

1 Answer 1

5
\$\begingroup\$

(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.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks for the suggestions! Making changes now. \$\endgroup\$
    – joseville
    Jun 12 at 5:51
  • \$\begingroup\$ I would argue that doing binary search on the precomputed partition values (i.e. p = bisect_left(self.part, target)) is just a different way of doing standard Exponential Search's first step: ``` bound = 1 while bound < self.N and self.nums[bound] < target: bound <<= 1 ``` and it's a more efficient way of doing the first step of Exponential Search when we're going to Exponential Search the same list many times. Indeed, I added the above bound = 1 ... snippet + assert bound == 1 << p to each of find_left and find_right, reran the tests, and got no assertion errors. \$\endgroup\$
    – joseville
    Jun 12 at 5:51
  • 1
    \$\begingroup\$ Was advised not to make changes to OP code, but I am updating locally with the suggestions. \$\endgroup\$
    – joseville
    Jun 12 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.