Spiral Linear Search (My Own)

Here, I am introducing a new way of searching for items. No matter whether items are sorted or unsorted.

Motivation

As you know we have many algorithms to perform searching. Some of them are:

• Linear search:- Iterative in the manner (Brute force)
  Time Complexity: O(n),
  Space Complexity: Constant Space
  Limitation: If the target element is at end of the list it takes N steps.
• Binary Search:- Recursive or In-Place iterative
  Time Complexity: O(logn)
  Space Complexity: Constant Space
  Limitation: The array should be pre-sorted. If the target element is very close (Suppose at the 2nd position) or very far (Suppose at the last position), It takes time to reach there.

This demands a new strategy to perform searches. Here comes …

Spiral Search

• It may follow an iterative or recursive approach.
• This search will work for unsorted arrays and also sorted arrays after little modification.
• Overcome limitations of Linear and Binary Search.
• This algorithm checks 3 places at once.

Example: A = [1, 3, 5, 7, 9, 10, 8, 6, 4, 2]

Algorithm

- Create low (start index), hi (last index), key (item to search) 
- check if low >= hi then return -1
- Find out mid. mid = low + (hi-low) // 2
- check if key is at low position, if true return the index
- Check if key is at hi position, if true return the index
- check if key is at mid position, if true return the index
- repeat the steps again with low+1, hi-1 for the same list

• Time Complexity -> O(n)
  Although the time complexity based on Asymptotic analysis is O(n) It performs better than it looks. To better understand one can use Amortized analysis which is another measurement to analyze the time complexity.
• Space complexity -> Constant space

import numpy as np
# Recursive approach
def spiral_search_recursive(arr, low, hi, key):
    if low >= hi:
        return -1
    
    mid = low + (hi-low) // 2
    
    if arr[low] == key:
        return low
    
    if arr[hi] == key:
        return hi
    
    if arr[mid] == key:
        return mid
    
    return spiral_search_recursive(arr, low+1, hi-1, key)
# Iterative approach
def spiral_search_iterative(arr, low, hi, key):
    while low < hi:
        mid = low + (hi-low) // 2
        if arr[low] == key:
            return low
        if arr[hi] == key:
            return hi
        if arr[mid] == key:
            return mid
        
        low += 1
        hi -= 1
    
    return -1
arr = np.random.randint(1, 10**6, 10**9)
print(spiral_search_iterative(arr, 0, len(arr) -1, 908500))

Thanks, Happy Coding!!