In this post, We will learn What is searching and what are the different types of searching algorithms we have in the data structure.
What is Searching?
In computer science, searching is the process of finding an item with the specified properties from a collection of items. The items may be stored as records in a database or a simple data element in the array, text in files, nodes in trees, vertices, and edges in graphs or they may be elements of other search spaces.
Why do we need searching?
Searching is one of the computer science algorithms. You know that today’s modern computers store a lot of information. To read this information proficiently, we need very efficient searching algorithms.
There are certain ways of organizing data that improves the searching process. That means If we keep the data in proper order it is easy to search the required elements. Sorting is one of the techniques for making the elements order. In this post, we will see different searching algorithms.
Types of Searching
The following are the types of searching available in computer science.
- Unordered Linear Search
- Sorted/Ordered Linear Search
- Binary Search
- Interpolation Search
- Symbol tables and hashing
- String searching algorithms: Ternary search,Tries and Suffix trees
Unordered Linear Search
Let us assume, we have given an array where the order of the elements is not known. That concludes the elements of the array are not sorted. In this case, to search for an element, we have to scan the complete array and see if the element is there in the given array or not.
|
1 2 3 4 5 6 7 |
public int unorderedLinearSearch(int inputArr[],int searchKey) { for (int i = 0; i < inputArr.length; i++) { if(inputArr[i] == searchKey) return i; } return -1; } |
Sorted/Ordered Linear Search
If the elements of the array are already sorted then in most cases, we don’t really have to scan the complete array to see if the element is there in the given array or not. In the algorithm below, It can be seen that at any point if the value at intputArr[i] is greater than data to be searched then we just return -1 without searching the remaining array.
|
1 2 3 4 5 6 7 8 |
public int orderedLinearSearch(int inputArr[],int searchKey) { for (int i = 0; i < inputArr.length; i++) if(inputArr[i] == searchKey) return i; else if (inputArr[i] > searchKey) return -1; return -1; } |
The time complexity of this algorithm is O(n). This is because it is the worst. We need to scan the complete array but in the average case, it reduces the complexity even though the growth rate is the same. Space complexity:O(1)
Binary Search
Binary search is one of the search techniques. Which works efficiently on the sorted arrays or collection. Hence, in order to search an element in array or collection by using binary search techniques, we must ensure that the array or collection is sorted.
The binary search uses a divide and conquer algorithm in which, the arrays or collection is divided into two halves and the item is compared with the middle element of the collection. If the match is found for a given searching key then the location of the middle element is returned. Otherwise, we have to search into either of the halves depending upon the result produced through the match.
The complete implementation of Binary search is Here
Interpolation Search
Click Here to know more about Interpolation Seach
You May Also Like:
Java program for linear search using the Iterative Approach
Java program for linear search using Recursive Approach
Java program for Binary search using Iterative Approach
Java program for binary search using the Recursive Approach
That’s all about What is Searching? Why do we need Searching? Explain different types of Searching?
If you have any feedback or suggestion please feel free to drop in below comment box.