Let’s start with the introduction to the Searching with some searching algorithm in the data structure below, you can also visit other articles on the Data Structure before start with searching with a searching algorithm.
Introduction to Searching
Searching is a process of finding a particular element or its position in a given array or list. If the element is found then the search is successful. if the element is not found in an array then the search is said to unsuccessful.
Two important and useful techniques for searching are Linear Search and Binary Search lets see both of them in detail below;
Linear searching in Data Structure
In this search particular element is searched sequentially in the whole given list. Suppose A is a linear array with N elements. For searching a KEY_ELEMENT in array A there is a need to compare KEY_ELEMENT with each element of array A one by one in a sequence.
Algorithm for linear searching
LINEAR_SEARCH [ i, key_element, a, n, loc]
In the below algorithm i keeps the track of comparison sequentially, n is a number of items in an array a. Key_element is an element that is to be searched and loc is a variable that will
hold the position(location) of key_element if it is found in array a otherwise it’s value remains -1.
- initialize i=0, and loc=-1.
- Repeat steps 3,4 while i<=n-1 otherwise move to step 5
- IF key_element = = a[i] then
- loc=i [assign the value of i to loc]
- move to step 5 & exit from repetation.
- i = i+1
- IF loc = = -1 then PRINT element is not found ELSE PRINT element and its locaton.
Binary Searching in Data structure
Binary search is a very efficient method for searching an element in a sorted list. In this searching we find the middle element, middle element divides the given list or array in the first half and second half.
Those elements belong to the first half which comes before the middle element and the second half includes that element that resides after the middle element. Then we compare the middle element of the list with key_element.
If key_element is greater then mid element it means searching element exist after the middle element so we ignore the first half of the list and consider only the second half.
If key_element is less then mid element it means searching element exists before the middle element so we ignore the second half of the list and consider only the first half.
And this process is continued until the searching element is not found. In this search, the location of the searching element is automatically locked in the location of the middle element.
Algorithm of binary searching
BINARY_SEARCH [ a, key_element, BEG,END, n, MID]
In the below algorithm BEG will keep the track of the first element, END will keep the track of the last element and MID will keep the track of middle element of the considered list. a is an array with n elements in which key_element is to be found.
- Initialize BEG = 0, END = n-1
- Set MID = (BEG+END)/2
- IF KEY_element > a[MID] then Set: BEG=MID+1 [ignoring the first half] Else Set: END=MID-1 [leaving the second half]
- Repeat STEPS 2,3 while KEY_element !=a [MID] AND BEG<=END otherwise move to step 5
- IF KEY element = = a[MID] then PRINT element is found
The efficiency of Binary Search
Now, let’s analyze how many comparisons (guesses) are necessary when running this algorithm on an array of n items.
- First, let’s try n = 100:
- After 1 guess, we have around 50 items left,
- After 2 guesses, we have around 25 items left,
- After 3 guesses, we have around 12 items left,
- After 4 guesses, we have around 6 items left,
- After 5 guesses, we have around 3 items left,
- After 6 guesses, we have around 1 item left
- After 7 guesses, we have around 0 items left.
The reason we have to list that last iteration is that the number of items left represents the number of other possible values to search. We need to reduce this to 0.
Also, note that when n is odd, such as when n=25 when we search the middle element, element #13, there are 12 elements smaller than it and 12 elements larger than it, so that’s why the number of items is slightly less than 1/2 in those cases.
In the general case, we get something like:
- After 1 guess, we have n/2 items left,
- After 2 guesses, we have n/4 items left,
- After 3 guesses, we have n/8 items left,
- After k guesses, we have n/2k items left.
If we can find the value that makes this fraction 1, then we know that in one more guess we’ll narrow down the item:
- 2nk = 1
- n= 2k
- k= log2 n
This means that a binary search roughly takes log2n comparisons when searching for a value in a sorted array of n items. This is much, much faster than searching linearly. Consider the following chart:
Basically, any algorithm that takes log2n steps is super fast.
Comment you like or not our article on Searching with a searching algorithm, and you can also visit our other article by click here.