Searching Algorithums : Linear Search | Binary Search | Interpolcation Search | exponential Search

searching.py

#------------------------------------------------
#------------Searching Algorithms----------------
#------------------------------------------------

'''

Searching Algorithm:
  1. Linear Search : Iterative and Recursive
  2. Binary Search : Iterative and Recursive
  3. Interpretation Search : Iterative
  4. Exponential Search : iterative

'''

#////////////// Linear Search////////////////////

#iterative solution
def linearSearch(array,l,h,value):
    for i in range(l,h):
        if array[i] == value:
            return i
    return -1

# recursive solution
def linearSearch1(array,l,h,value):
    if l > h :
        return -1
    if array[l] == value:
        return l
    if array[h] == value:
        return h
    return linearSearch1(array,l+1,h-1,value)


#///////////// Binary Search ////////////////////

# iterative solution
def binarySearch(array,l,h,value):
    while True:
        mid = (h+l)//2
        if array[mid] == value:
            return mid
        elif array[mid] > value:
            h = mid -1
        else:
            l = mid +1
        if l == h : break    
    return -1

# recursive solution
def binarySearch1(array,l,h,value):
    if l == h and array[l] != value:
        return -1
    if array[l] == value:
        return l
    elif array[l] > value:
        return binarySearch1(array,l,(h+l)//2 -1,value)
    else:
        return binarySearch1(array,(h+l)//2 + 1,h,value)


#///////////// Interpolation Search////////////////////

def interpolationSearch(array,l,h,value):
    while l <= h and array[l] <= value and array[h] >= value:
        if l == h:
            if array[l] ==  value:
                return l
            return -1        
        index = l + (((value - array[l])*(h-l))//(array[h]-array[l]))
        if array[index] == value:
            return index
        elif array[index] > value:
            h = index - 1
        else:
            l = index + 1
    return -1


# //////////////// Exponential Search //////////////////////

def exponentialSearch(array,value):
    if array[0] == value:
        return 0
    if array[0] > value:
        return -1
    i = 1
    while i < len(array) and array[i] < value:
        if array[i] == value:
            return i
        i = i*2
    return interpolationSearch(array,i//2,i,value)

#-------testing---------

if __name__ == "__main__":

    array = [x for x in range(0,50,3)]
    print(array)
    find = 25
    print(exponentialSearch(array,find))
    print(linearSearch(array,0,len(array)-1,find))
    print(linearSearch1(array,0,len(array)-1,find))
    print(binarySearch(array,0,len(array)-1,find))
    print(binarySearch1(array,0,len(array)-1,find))
    print(interpolationSearch(array,0,len(array)-1,find))