Searching - DSA | Part 3 |

Searching is the process to find the element and its position in the given array/list.

We'll discuss two searching algorithms which are Linear Search & Binary Search and finding which one is better.

Linear Search

Linear Search is a basic searching algorithm. It searches an element from the entire list.

It is very time consuming algorithm because if we search the last index of element , then this algorithm will start searching from beginning and it traverses the entire list until the element is found.

For example, if we have a list which contains 100 elements and we want to find 100th element of the list, then Linear search will compare each element one by one and it will do 100 comparison which is very time consuming.

Algorithm

LinearSearch(array, key)
  for each item in the array
    if item == value
      return index

Implimentation of Linear Search

# Linear Search

def linearSearch(array, size, key):

    for i in range(0, size):
        if (array[i] == key):
            return i
    return -1


array = [2, 4, 0, 1, 9]
key = 1
size = len(array)
result = linearSearch(array, size, key)
if(result == -1):
    print("Element not found")
else:
    print("Element found at index: ", result)

Time Complexity

Time complexity of Linear Search is O(n) because in the algorithm loop will run 'n' times to search the element.

Space Complexity

Space Complexity of Linear Search is O(1) because it does not take extra space/memory while searching.

Binary Search

Binary Search is a searching algorithm for finding an element's position in a sorted array.

In this approach, the element is always searched in the middle of a portion of an array.

Algorithm

do until the pointers low and high meet each other.
    mid = (low + high)/2
    if (x == arr[mid])
        return mid
    else if (x > arr[mid]) // x is on the right side
        low = mid + 1
    else                       // x is on the left side
        high = mid - 1

Implimentation of Binary Search

# Binary Search

def binarySearch(array, key, low, high):
    while low <= high:

        mid = low + (high - low)//2

        if array[mid] == x:
            return mid

        elif array[mid] < x:
            low = mid + 1

        else:
            high = mid - 1

    return -1


array = [3, 4, 5, 6, 7, 8, 9]
key = 4

result = binarySearch(array, key, 0, len(array)-1)

if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Not found")

Time Complexity of Binary Search

• Best Case - O(1)
• Average Case - O(log n)
• Worst Case - O(log n)

Space Complexity of Binary Search

Space Complexity of Binary Search is O(1) because it does not take extra space/memory while searching.

So that's it for today. I hope you like this post. Share this post to your friends/relatives to spread the knowledge.

Thank you.