Random search

Random search ''does not require data to be ordered/sorted''.

Random search (simple implementation): randomly select some point (an index in the array) then again and again. The trick only is to avoid repeating of random indexes. We do it by excluding missing index from the next random generation. How? We generate random index from ''some range''. If the index is missing then we change the range:

_
1 2 3      ->  2..3              (1)
    _
1 2 3      ->  1..2              (2)
  _
1 2 3      ->  1..1, 3..3        (3)
    _
1 2 3 4 5  ->  1..2, 4..5        (3)
_
1 2        ->  2..2              (1)
  _
1 2        ->  1..1              (2)
_
1 1        ->  []                (1)

Actually we have only 3 cases with optional normalization (when after the removal operation the range becomes abnormal: left > right which means that it must be empty now, ie, excluding from generating at all).

What does it mean "excluding from generating" for a range? We generate random indexes from ''random ranges'' - this means it - we exclude the range itself, so we cannot generate indexes from it more.

import random

class Rng:
    '''Range'''
    def __init__(self, i0, i1):
        self.i0 = i0; self.i1 = i1
    def __len__(self): return self.i1 - self.i0 + 1
    def __repr__(self): return f'{self.i0}..{self.i1}'
    def isnormal(self): return self.i0 <= self.i1


def exclude_pt(rng, i):
    # Exclude the point (random index) from the range
    # BCS it is missing, so it should not participate
    # in random indexes generation more.
    # The result may be a new range(s) or no more
    # new range
    if i == rng.i0:
        res = [Rng(rng.i0 + 1, rng.i1)]
        if not res[0].isnormal():
            res = []
    elif i == rng.i1:
        res = [Rng(rng.i0, rng.i1 - 1)]
        if not res[0].isnormal():
            res = []
    elif rng.i0 < i < rng.i1:
        res = [Rng(rng.i0, i - 1), Rng(i + 1, rng.i1)]
    else:
        raise ValueError(f'Invalid pt {i} for range {rng}')
    return res


def rndsearch(arr, target):
    _tested = set()
    ranges = [Rng(0, len(arr) - 1)]
    while True:
        rngi = random.randint(0, len(ranges) - 1)
        rng = ranges[rngi]
        i = random.randint(rng.i0, rng.i1) if len(rng) else rng.i0

        # Assert that no repeated tests
        assert i not in _tested, f'{i} already tested!'
        _tested.add(i)
        
        if arr[i] == target:
            return i
        else:
            if rng:
                new_rngs = exclude_pt(rng, i)
                if new_rngs:
                    ranges[rngi] = new_rngs[0]
                    if len(new_rngs) > 1:
                        new_rngi = rngi + 1
                        if new_rngi >= len(ranges):
                            ranges.append(new_rngs[1])
                        else:
                            ranges.insert(rngi + 1, new_rngs[1])
                else:
                    del ranges[rngi]
            else:
                del ranges[rngi]
        # Did we completed?
        if len(ranges) == 0:
            return -1


#########################
class ACCESS(list):
    def __init__(self, *a, **kw):
        super().__init__(*a, **kw)
        self._access = 0
    def __getitem__(self, i):
        if i >= len(self):
            print(f"{self._access}: [{i}]=OUT OF RANGE!")
        res = super().__getitem__(i)
        print(f"{self._access}: [{i}]={res}")
        self._access += 1
        return res


def partiallyrandomdata(num, ratio=0.5):
    res = list(range(num))
    i = 0
    cnt = min(num, num*ratio)
    while i < cnt:
        r = random.randint(num, num + cnt - 1)
        res[r - num] = r
        i += 1
    res = sorted(res)
    return (res, random.choice(res))


NUM = 100
arr, x = partiallyrandomdata(NUM, 1)
print(f"Look for {x} in {arr}")
try:
    fnd = rndsearch(ACCESS(arr), x)
    if 0 <= fnd < NUM:
        print(f"Found {x} at {fnd}: {arr[fnd]}")
    else:
        print(f"{x} not found")
except KeyboardInterrupt:
    print(f"Looked for {x} in {arr}")