Searching is an operation of finding the specific data or related data present in a file, an array, in a linked list, or any data structure.
What is searching for?
Searching is a process of finding any given data in a large collection of data.
In memory, data is organized in an array, linked list, graph, and tree, etc.
If required data is available in a file or any data structure, we will get a related output otherwise to get no item found or any customizable message.
We can perform a searching operation in both primary and secondary memory.
The complexity of the searching algorithm depends on the number of comparisons required to find specific data from the data collection.
There are two types of searching technique
a). Sequential Search
b). Binary Search
a). Sequential Search
- A sequential search is applied when data is arranged in an unsorted form.
- A sequential search is also known as a Linear search because it compares each element from the beginning.
- A sequential search is a very basic search.
- The search starts from the beginning of the array or list, and it will go at the end of matches not found anywhere on the list.
In a sequential search, each element of a list or an array is traversed and compare with the search element until a match is found. If a match is found, then it will return the index value; otherwise, it will return -1.
The worst-case and Average case Complexity of linear search is O(n).
The best-case complexity of the linear search is O(1).
b). Binary Search
- Binary search is applied when data is arranged in a sorted form, an array, or a linked list.
- In Binary search, each element is not traversed and compared. Here we first find the middle element and compare it with the search value. If the search value is smaller than the middle value, we will further compare only the first half elements. And if the search value is greater than the middle value, then we will do a further comparison on only the second half elements.
- It is a faster searching technique in comparison to the linear searching technique because it won’t compare each element of an array and list.
The worst-case and Average case Complexity of Binary search is O(log n).
The best-case complexity of Binary search is O(1).
- Data and collection of data are stored in memory. When we perform any search operation, then in return, we will get our desired output like data for which we are looking for in case if our data is present in memory. But if our data is not present, we are looking for, and we will get some output like “data not found” or any customizable output.
- In memory, data is organized in the form of a linked list, an array, a graph, or a tree. And search operation depends upon how data is organized in memory. There are various searching algorithms that depend on how data is organized in memory.
- Data are available in both memory primary memory and secondary memory. When we perform a search on primary memory, then it is known as internal searching. And when we perform a search on secondary memory, then it is known as external searching.
- Our data or table of data is present in both memories, primary as well as secondary. Large and persistent data is present in secondary memory, and data on which some operation is performing stay on primary memory.
- There are many searching algorithms. And a selection of this algorithm depends upon how data is organized in memory.
[wpusb]