Searching is the process of finding a particular element from a long list of multiple elements. If you are a programmer and working with data stored in Linear data structures like arrays, I bet you must have come across needing a search operation. In this article let's take a look at the two of the most used searching algorithms.
- Linear Search
- Binary Search
Linear Search
Consider that you want to eat your favourite food, but that food is present in an only restaurant among multiple restaurants present in a food fest. What you will do is go one by one to restaurants and search for your favourite food.
The above method is simply called Linear Search. When there are multiple elements present in the array, the best and the easiest way of searching is going one by one and checking the elements by comparing them.
Below is a simple explanation of Linear Search Implementation in Python.
def linearSearch(array, n, target):
for i in range(0, n):
if (array[i] == target):
return i
return -1
array = [10, 20, 30, 40, 50]
x = 30
n = len(array)
result = linearSearch(array, n, x)
if(result == -1):
print("Element not found")
else:
print("Element found at index: ", result)
Time Complexity:- In the best case, if the element you want to search is present at the first index, the time complexity is O(n). But time complexities are measured based on worst cases since it is considered the best parameter to measure the time consumed by the algorithm. So over here we can see a case where the element could be present at the end of the array. So the time complexity is the no of elements in the array which is O(n)
Space Complexity:- Since we are not using any external data structure, the space complexity remains constant at O(1).
Advantages:-
- Easy to understand.
- Works in all cases (both sorted and non sorted).
- Space efficient.
Disadvantages:-
- Not so time-efficient when compared to binary search on sorted elements.
Binary Search
Imagine when the elements you operating on is sorted in some way (either ascending or descending). So now you have a slight understanding of where your search element must be present. This approach is called Binary Search.
In this approach, there will be three-pointers (start, end and middle). At first, the start will be at zero indexes and the end will be at last. Consider an example in which the array is ascending sorted, in the first iteration of binary search we will find the middle pointer by float dividing (start + end) by 2. If the element is found we return the mid pointer, else if the current mid element is greater than the target we decrease the end element by (mid - 1) else if the current mid element is lesser than the target we increase the start element. This process continues until we find the target.
Below is a simple explanation of Binary Search Implementation in Python.
def binarySearch(arr, target, low, high):
while low <= high:
mid = low + (high - low) // 2
if arr[mid]==target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
arr = [10, 20, 30, 40, 50, 60, 70]
x = 30
result = binarySearch(arr, x, 0, len(arr)-1)
if result != -1:
print("Element is present at index " + str(result))
else:
print("Not found")
Time Complexity:- Binary Search is an example of a divide and conquer algorithm. In each iteration of the binary search, we are reducing our no if inputs. For example in the above input when comparing the start and the end ranges of the code we have 7 inputs but since it didn't fit our condition we break it into 3 elements and then one. So here is no of the elements is decreasing so our time complexity is the worst case also could be O(logn), which is more efficient than linear search when compared.
Space Complexity:- Since we are not using any external data structure, the space complexity remains constant at O(1).
Advantages:-
- Time efficient when using sorted elements.
- Space efficient.
Disadvantages:-
- Works only in sorted cases. If the element is not sorted, we have to first sort the elements and then search using Binary search which is not efficient when compared to Linear search on non-sorted elements since it remains the same for both cases.
Conclusion
Searching is one of the important operations in the linear data structure. If you find yourselves in a situation where the array is sorted and want to search use Binary Search, else stick with Linear Search.
Thank you.
