Sequential Scan

This method traverses the collection element by element starting from the first index. It imposes no constraints on data ordering, functioning effectively on both sorted and unsorted sequences. The process terminates immediately upon finding the target value.

def sequential_scan(arr, key):
    """
    Scans a list to find a specific integer.
    
    Args:
        arr: List of integers to search through.
        key: Target value to locate.
        
    Returns:
        int: Index of the target, or -1 if not present.
    """
    iteration = 0
    for index in range(len(arr)):
        iteration += 1
        print(f'Iteration #{iteration}')
        if arr[index] == key:
            return index
    return -1

if __name__ == "__main__":
    sample_data = [10, 20, 30, 45, 55, 67, 69, 73, 89, 92, 100]
    separator = "*" * 30
    
    result1 = sequential_scan(sample_data, 100)
    print(separator)
    print("Match found" if result1 != -1 else "No match")
    
    result2 = sequential_scan(sample_data, -1)
    print(separator)
    print("Match found" if result2 != -1 else "No match")

Console Output

******************************
Iteration #1
Iteration #2
...
Iteration #11
Match found
******************************
Iteration #1
...
Iteration #11
No match

Halving Technique

Applicable only to sorted datasets, this algorithm divides the search space in half during each step. By comparing the middle element against the target, it discards the irrelevant half of the remaining candidates.

def halving_search(arr, key):
    """
    Performs binary search on a sorted sequence.
    
    Args:
        arr: Sorted list of integers.
        key: Value to search for.
        
    Returns:
        int: Index of the target, or -1.
    """
    lower_bound = 0
    upper_bound = len(arr) - 1
    iteration_count = 0
    
    while lower_bound <= upper_bound:
        iteration_count += 1
        print(f'Iteration #{iteration_count}')
        mid_index = (lower_bound + upper_bound) // 2
        
        if arr[mid_index] == key:
            return mid_index
        elif arr[mid_index] > key:
            upper_bound = mid_index - 1
        else:
            lower_bound = mid_index + 1
    return -1

if __name__ == "__main__":
    data_pool = [10, 20, 30, 45, 55, 67, 69, 73, 89, 92, 100]
    border = "*" * 30
    
    out1 = halving_search(data_pool, 100)
    print(border)
    print("Success" if out1 != -1 else "Failure")
    
    out2 = halving_search(data_pool, -1)
    print(border)
    print("Success" if out2 != -1 else "Failure")

Position Estimation

An optimization over halving search for uniformly distributed values. Instead of picking the exact center, it calculates a probable position based on the value magnitude relative to the endpoints.

def position_estimation(arr, key):
    """
    Uses interpolation to guess the key's location.
    
    Args:
        arr: Sorted list with uniform distribution.
        key: Target integer.
        
    Returns:
        int: Location index or -1.
    """
    low_idx = 0
    high_idx = len(arr) - 1
    steps = 0
    
    while low_idx <= high_idx and arr[low_idx] <= arr[high_idx]:
        steps += 1
        print(f'Step #{steps}')
        
        try:
            pos = low_idx + int(((key - arr[low_idx]) / 
                          (arr[high_idx] - arr[low_idx])) * (high_idx - low_idx))
        except ZeroDivisionError:
            break
            
        if arr[pos] == key:
            return pos
        elif arr[pos] < key:
            low_idx = pos + 1
        else:
            high_idx = pos - 1
    return -1

if __name__ == "__main__":
    dataset = [10, 20, 30, 45, 55, 67, 69, 73, 89, 92, 100]
    line = "*" * 30
    
    res_a = position_estimation(dataset, 100)
    print(line)
    print("Found" if res_a != -1 else "Missed")
    
    res_b = position_estimation(dataset, -1)
    print(line)
    print("Found" if res_b != -1 else "Missed")

Ratio-Based Splitting

Leverages the Fibonacci sequence to partition the array. This avoids division operations, relying instead on addition and subtraction which can be faster on certain hardware architectures. The split points approach the golden ratio.

def generate_fib(max_val):
    fib_series = [0, 1]
    while fib_series[-1] < max_val:
        fib_series.append(fib_series[-1] + fib_series[-2])
    return fib_series

def ratio_splitting(arr, key):
    """
    Implements search using Fibonacci numbers.
    
    Args:
        arr: Sorted list.
        key: Target number.
        
    Returns:
        int: Index or -1.
    """
    fib_vals = generate_fib(len(arr) + 1)
    offset = 0
    idx_fib = 0
    counter = 0
    
    while len(fib_vals) - 1 > 1:
        counter += 1
        print(f'Turn #{counter}')
        i = min(offset + fib_vals[idx_fib - 1], len(arr) - 1)
        
        if arr[i] < key:
            idx_fib -= 1
            offset = i
        elif arr[i] > key:
            idx_fib -= 2
        else:
            return i
    
    if offset < len(arr) and arr[offset] == key:
        return offset
    return -1

if __name__ == "__main__":
    pool = [10, 20, 30, 45, 55, 67, 69, 73, 89, 92, 100]
    dash = "*" * 30
    
    val_1 = ratio_splitting(pool, 100)
    print(dash)
    print("Hit" if val_1 != -1 else "Empty")
    
    val_2 = ratio_splitting(pool, -1)
    print(dash)
    print("Hit" if val_2 != -1 else "Empty")