Algorithm is a step-by-step set of instructions for completing a task. This is regardless of the language being used hence, it can be written in more than one language.
In this series, we will look at various forms of algorithms. But first,
Let us understand:
Sorted and Unsorted Search
Linear and Binary Search
.
Sorted and Unsorted Search
A sorted search is a search that has been sorted. In other words, this search is arranged from lowest to highest while an unsorted search is a search that has not been arranged.
.
Linear search
Linear search is an algorithm we can use to find an element in an array.
How it works: It iterates across the array from left to right looking for a specific element.
If the first element is the element you are looking for, you stop. Else, if it is not the element you are looking for, you proceed until you find the element in the array you need else if you don’t find it at the end of the array, you stop.
This starts from the first down to the last till it is found
Let us look at an example of linear search:
Say an array arr is
[12, 4, 8, 9, 6, 7]
and you want to find the number 6. You will iterate from left to right of the array to find the number 6. When you get there, you stop the iteration and end the search. So we start from the first, till the second till we find 6. Then we stop.
What if we are looking for say 18? We won’t know if 18 is part of the array until we move through each element till arriving at the last then we can conclude that 18 is not part of the array.
The Worst-case scenario of linear search:
In the worse case, the value is the last element or does not exist.
Here, we have to go through the entire array arr of n elements, either because the target element of the array is the last element or it does not exist in the array.
Binary search
This starts from the middle and goes towards the right or left depending on the value he is looking for and the value he has in the middle. This is possible because the array is sorted. It is faster as you search from the middle. This is similar to divide and conquer. Divide from the middle and proceed.
.
The Best-case scenario:
The best case scenario is that the element is the first element in the array hence, we can stop searching immediately after the first search.
Based on the best and worst case scenarios, the complexity of linear search can be seen as follows:
The worse case runs in O of n represented as O(n) while the worse case runs in omega of 1 represented as omega(1)
Running Time: How much is binary search better than linear search
if you compare the time it took to run a binary search and the time it took to run a linear search, we want to see the time difference. Formulas we can use to analyze algorithms:
O(n2), O(n log n), O(n), O(log n), O(1)
.
In the worse case of linear search: it will take
O(n)
In the worse case of binary search, it will take
O(log n)
Follow me on Twitter Handle: https://twitter.com/mchelleOkonicha
Follow me on LinkedIn Handle: https://www.linkedin.com/in/buchi-michelle-okonicha-0a3b2b194/
Top comments (0)