Skip to main content

Searching

How it works ?

Go through each element one by one. When the element you are searching for is found, return its index.

linear_search.py
def linear_search(lst, key):
    if len(lst) <= 0:
        return -1
    for i in range(len(lst)):
        if lst[i] == key:
            return i
    return -1


# Driver code to test above
if __name__ == "__main__":

    lst = [5, 4, 1, 0, 5, 95, 4, -100, 200, 0]
    key = 95

    index = linear_search(lst, key)
    if index != -1:
        print("Key:", key, "is found at index:", index)
    else:
        print(key, " is not found in the list.")

Complexity

  • Time complexity: O(n)

How it works ?

Assuming that the input array is sorted, compare the element that is being searched for with the element at the middle of the array. If the element being searched for is greater than the element at the middle of the array, recursively check for it in the second half of the given array. Otherwise, search for it in the first half of the given array.

How to implement ?

The element to be searched is compared with the element at the middle index. If it matches, the index of the middle element is returned. If it does not match, we check if the element is greater or smaller than the middle element.

If the element at the middle is smaller than the element, the left index is accordingly updated to be mid + 1. In this way, we ignore the left half of the array.

Similarly, if the element at the middle is greater than the element that we’re searching for, the element we’re searching for is in the initial half of the list. Hence, the right index is updated to be mid - 1. In this way, we ignore the right half of the array.

We iterate over the left or right half of the array by comparing the key with the middle element mid and continue iterating until the index of the search element is found, or the array is fully traversed in that particular half. If the required number exists, its index is returned. And if it does not, -1 is returned, indicating that the searched number does not exist.

binary_search.py
def binary_search(lst, left, right, key):
    """
    Binary search function
    :param lst: lst of unsorted integers
    :param left: left sided index of the list
    :param right: right sided index of the list
    :param key: A key to be searched in the list
    """

    while left <= right:

        mid = left + (right - left) // 2

        if lst[mid] == key:
            return mid
        elif lst[mid] > key:
            right = mid - 1
        else:
            left = mid + 1

    return -1


# Driver to test above code
if __name__ == "__main__":

    lst = [1, 2, 3, 10, 20, 40, 111, 244, 14444, 800000]
    key = 111

    # Function call
    result = binary_search(lst, 0, len(lst) - 1, key)

    if result != -1:
        print("Element is present at index:", result)
    else:
        print("Element is not present in the list")

Complexity

  • Time complexity: O(log(n))