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.
Top comments (0)