BinarySearch.py

"""
Binary Search Algorithm
    Search Algorithm that finds the position of a target value within a sorted array(ASCE).
    Binary search compares the target value to the middle element of the array.
    Normal Zindagi (Linear Search):
        To find an element from a list, compare elements from index[0] till the element is found
    Mentos Zindagi (Binary Search):
        To find an element k from a list:
            > Sort the array in Ascending order
            > Find the middle element from the list
            > Compare it with key to be found
                > If middle element is less than key, find the middle element of the list at right-side of the middle element
                > If middle element is more than key, find the middle element of the list at left-side of the middle element
                > Repeat above 2 steps until the key is found
                > Return index of the key if it is found in the list
                > If key is not found in the list, return -1 or false
        With every iteration, search space is divided by 1/2
            Iteration 1 = n/2
            Iteration 2 = (n/2)/2 = n/2^2
            Iteration 3 = (n/2^2) = n/2^3
            Iteration k = (n/2^k)
                1 = n/2^k
                n = 2^k
                log2(n) = log2(2^k)
                log2(n) = k*log2(2)
                k = log(n)
            Time Complexity: O(log n)


key: 18
2 4 6 8 |10| 12 16 18 20    :: key not in {2, 4, 6, 8, 10}
~2 4 6 8 10~ 12 |16| 18 20  :: key not in {12}
~2 4 6 8 10 12 16~ |18| 20  :: key found in {18} at index[7]
Output:
7

Linear Search   7 iterations    O(n)
Binary Search   3 iterations    log(n)
"""

def LinearSearch(numList, key):
    for index, element in enumerate(numList):  # return index as well as element
        if element == key:
            return index  # if key is found in list, return index of key
    return -1

def BinarySearch(numList, key):
    left = 0  # index of elements at left of the mid value
    right = len(numList) - 1  # index of elements at right of the mid value
    mid_index = 0  # index of mid value

    while left <= right:  # while index[left] <= index[right]
        mid_index = (left + right)  // 2  # '//2' returns integer value
        mid_num = numList[mid_index]

        if mid_num == key:  # middle number is equal to key
            return mid_index
        if mid_num < key:
            left = mid_index + 1
        else:  # mid_num > key
            right = mid_index - 1

    return -1


"""Binary Search using Recursion"""
def BinarySearchRecursion(numList, key, leftIndex, rightIndex):  # will search within left and right
    if rightIndex < leftIndex:  # won't iterate in reverse order
        return -1

    mid_index = (leftIndex + rightIndex) // 2  # '//2' returns integer value
    if mid_index >= len(numList):  # if key is out of index of list, return -1
        return -1

    mid_num = numList[mid_index]
    if mid_num == key:  # middle number is equal to key
        return mid_index

    if mid_num < key:
        leftIndex = mid_index + 1
    else:  # mid_num > key
        rightIndex = mid_index - 1

    return BinarySearchRecursion(numList, key, leftIndex, rightIndex)






if __name__ == '__main__':
    numList = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
    key = 18
    # Linear Search
    index = LinearSearch(numList, key)
    print(f"Linear Search: Number found at index {index}")
    # Binary Search
    index = BinarySearch(numList, key)
    print(f"Binary Search: Number found at index {index}")
    # Binary Search using Recursion
    index = BinarySearchRecursion(numList, key, 0, len(numList))
    print(f"Binary Search Recursion: Number found at index {index}")