.png)
Searching
Searching
Searching is the process of finding an element in the desired list of elements. If we found the element then the search is said to successful and if not then is it said to be unsuccessful.
Two very popular search techniques are
Linear Search
Binary Search
Let us look at each one of them in detail
Linear Search
What is linear search?
It is basically like our normal search. In this search, a sequential search is made over all items one by one. Each item is checked and if a match is found then that particular item is returned, otherwise the search continues till the end of the data collection.
Understanding an Example
Let us look at an example
Very simple we can say that we go to each and every element, compare it with the value we want to find. If we find the value we stop the search and if don’t then we return the value -1.
Here in the example above 20 is compared with 10, 50, 30, 70, 80, and 60 but each time the value is not equal to the desired value therefore we continue and at 6th position, we find the element.
Therefore, position 6 is returned.
What we did
If we summarize what we did, we basically performed 3 very simple steps.
Started from the leftmost element and one by one compare all the elements with the desired value.
If the value from the array matches with the desired value we return the index.
If we don’t find the element, then we return -1.
Let us look at how will we implement it in the code.
In the example above we called the function with two parameters arr i.e an array and a key i.e the value which we want to search in the array.
The entire algorithm will be performed and we will see the result which will contain the position at which element will be found.
But what are the flaws in it?
But did you noticed one thing that if the required elements will be present at the last then we will have to travel through the entire array to find it?
I am sure you will say so that we just have 10 elements but in real-world when we use arrays we have hundreds and thousands of elements in each array and we can not go through them one by one because it will require a lot and lots of time and will explicitly decrease our speed.
So, we use another approach that helps us to do the same task in a more efficient manner. Let us have a look at it.
Binary Search
What is binary search?
Binary search is a type of search that is used to find a specific element in an Array but the only constraint with it is that it works only with the sorted arrays i.e we need our array to be sorted using any sorting technique that we discussed previously.
Working of binary search
Binary search works using divide and conquers algorithms. But what exactly is the divide and conquer algorithm? It means that we divide the array roughly into 2 parts to check whether we found our element or not and continue accordingly. Basically, we divide the problem into simpler problems until it becomes simple enough to be solved directly.
We define a midpoint from the element in the middle of the array(Divide) to see if we have matched our target or not.If our value is greater than the midpoint then we move towards the right and if our value is smaller than the midpoint then we move towards the left.
Understanding an Example
Let us take an example to have a firm understanding of the concept
In the example above we have to search 23, so we first start by taking the lower bound at 0 i.e. the start of the array, and upper bound at 0 i.e. the end of the array.
Simply we find the middle element, 0+9/2 i.e. 4.5 but we round it to 4.
So, now the element at index 4 i.e 16 is our middle element.
But that is not our desired element so we check whether our desired element is greater or less than the middle element. 23 >16 so we proceed towards the right side of the array.
We shift our lower bound to 5 i.e index[midpoint]+1, now we again find the midpoint and check with our desired element.23<56, so we move towards the left side of the array and shift the upper bound to index[midpoint]-1.
Again, we find our mid-value, and this time it is the exact value that we need.
So, our search ends here.
What we did
If we summarize what we have learned we basically did 4 steps
Set the upper and lower bound of the array and find the middle element with its help.
Compare the middle value with the value we are looking for
If the key is less than the middle element. Search in the left half.
If the key is more than the middle element, search in the right half.
If the key is equal to the middle element, return the index of the middle element.
Continue with step 1,2 until we are left with a single element.
If the value is not found then we return -1.
Let us look at how will we implement it in the code.
In the example above we called the function with two parameters arr i.e a sorted array and a key i.e the value which we want to search in the array.
The entire algorithm will be performed and we will see the result which will contain the position at which element will be found.