SDET: Easy Algorithms- Linear vs Binary search
Hi Dear, IT experts
Today, I want start talking about algorithms. And there is no easier way to start as to start from Search algorithms. Then, let’s start.
There are two of the most common used search algorithms:
- Linear search
- Binary search
Let’s jump and explain each of them
Linear Search Algorithm
This algorithm performs sequential search of the data in the array.
Let’s imagine you have some train and are looking for some passenger. You are moving from one carriage to another until you have not found it or you have come to the end of the train
Sounds very clear?
Let’s jump to code.
Let’s imagine we want to find index of passenger. All we need is to use for loop and follow each passengers:
Let’s use this method:
As simple as that!!!
Time Complexity: Since our search depends only on array size and we compare each element only once, it means we have Linear time O (n) complexity. Neverminded, just for information.
As you may understand, Linear search algorithm should be used in case when our list/array is not sorted.
For sorted array, it will be better to use the next search algorithm.
Binary Search Algorithm
This time, we sorted all our passengers in alphabetical order. Probably we can save our energy and search our passenger by splitting carriages on half until we have not found our passenger or not found if we don’t have such person.
- Let’s imagine we want to find “A”. We are calculating middle carriage. We have total six carriages. So, let’s divide six on half. It means carriage number three or “J”.
- First let’s verify if “A” equals to “J”. Not, it means that’s not the value we are looking for.
- Is “A” > “J” ? No. It means we should not search in carriages after J
So, let’ switch our highest carriage to “J”-1. Now, out highest carriage is “D”. Lowest will be the same — “A”.
- Next phase, let’s calculate middle again. We have left only two carriages. So, out middle will be 1 or “A”.
- let’s verify if “A” equals to “A”. Bingo. That’s how it works.
- I think now you understand a principle. It will work a similar way the in another direction. But this time you will change left edge index.
Now, let’s jump to the code:
So, we have an array with it’s lowers index and highest index. Also, we have a value we want to find.
public static bool BinarySearchRecUtil(int[] arr, int low, int high, int value)
We are planning to use this method recursively, so, let’s first verify if our low index is greater than high.
If it’s not, then it means we have already followed all array and nothing was found. So, we may return false.
if (low > high)
{
return false;
}
Next line, find current iteration middle index.
int mid = (low + high) / 2;
Let’s verify if our current middle index element is equal to search criteria
If yes, Bingo!!! We found.
if (arr[mid] == value)
{
return true;
}
The next, we want to verify if our current middle element is less than search criteria. If it is less, then let’s call our method adding middle+1 to our left index. So, we split half to the right part.
else if (arr[mid] < value)
{
return BinarySearchRecUtil(arr, mid + 1, high, value);
}
If previous verification was false, let’s do a similar operation, but in the different direction. This time we need to change our right edge index to the value middle -1
else
{
return BinarySearchRecUtil(arr, low, mid — 1, value);
}
Binary search looks a little bit harder then Linear. Anyway, it’s not so hard as you think. Please review code carefully a few times and you will get it.
Time Complexity: Every iteration of search you reduce array to the half. The time complexity of the Binary search is O(LogN) or Logarithmic time — O (log n)
So, as you may understand, this algorithm is best practice for Sorted Arrays. There is no reason to follow it sequentially if you can split it on half and compare results.
Ending
We learned a two of the most simplest algorithms. Anyway, if you want to develop you programming skills, it will be useful to be familiar with them.
Good luck!
Thank you!!!
