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

We'll discuss two searching algorithms which areLinear 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 SearchdeflinearSearch(array,size,key):foriinrange(0,size):if(array[i]==key):returnireturn-1array=[2,4,0,1,9]key=1size=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 isO(n) because in the algorithm loop will run 'n' times to search the element.

Space Complexity

Space Complexity of Linear Search isO(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 asorted 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 SearchdefbinarySearch(array,key,low,high):whilelow<=high:mid=low+(high-low)//2ifarray[mid]==x:returnmidelifarray[mid]<x:low=mid+1else:high=mid-1return-1array=[3,4,5,6,7,8,9]key=4result=binarySearch(array,key,0,len(array)-1)ifresult!=-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.