What is Searching:
Searching in data structure help to find a element from any form of data structure where it is stored.
Types of Searching:
There are two types of searching which are as follows:
Linear Searching
“Linear search, also known as sequential search, is a method in which an element is searched by comparing it one by one with each element in sequential order.”
For Example:
If we want to search 30 in the following Array:
Step-1 : Firstly, 30 is compared to first element that is 10
Step-2: When not matched then 30 is compared to second element that is 20
Step-3 When not matched then 30 is compared to third element that is 30
Step -4: Finally element is found
Binary Searching
Binary search can be applied on sorted array . It works by repeatedly dividing the array into half until element to be searched is found.
For Example:
If we want to search 30 in the following Array:
Step-1: Firstly the array is of 5 elements then it is divided by 2 that is 5/2 means 3 element is compared firstly.
Step-2 : 30 is the third element then it is compared with the element to searched.
Step -3: It is matched then the element is found.
Difference Between Linear and Binary Searching:
| Linear Search | Binary Search |
| To search in linear search element can be given in any order. | To search in Binary Search element should be in ascending order . |
| Preferred for small size. | Preferred for bigger size. |
| It is a slow process. | It is Faster than linear search. |
| Best Case Complexity : O(1) | Best Case Complexity: O(1) |
| Worst Case Complexity: O(n) | Worst Case Complexity : O(log2 n) |
| Based on Sequential Approach | Based on Divide and Conquer Approach |
| Implemented on Both Single and Multidimensional Array | Implemented on Single Dimensional Array only |
| Less Complex | More Complex than Linear Search |
| Time Complexity : O(n) | Time Complexity : O(log n) |
| Space Complexity: O(1) | Space Complexity: O(1) |
Related Link: