Data Structure and Algorithms: Linear Search
Tags: datastructure, algorithms, java, linearsearch
Published: 2020-11-18 17:16:59

# **What is Searching?**

In Computer Science, *searching* is "the process of finding an item with specified properties from a collection of items." An item can be anything from a stored record or an array element to elements of other search spaces. 
## But why do we need Searching? 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/3g96utpxe2ezee0lquyg.gif)

The answer is- to find the data that you are looking for, from a large set of data. For example, finding your friend's phone number from a long contact list can be made easier using searching algorithms. Here the contact list is the *collection of items* and your friend's number is the *data* with the specified property.

Some examples of searching algorithms are Linear Search, Binary Search, Interpolation Search, etc. Here we'll discuss Linear Search. 

# **What is Linear Search?**
Linear search is a simple searching algorithm that checks every item in a collection sequentially. If the match is found the item is returned, otherwise the search continues till the end of the collection. 
Assume that you are given an array where the order of the elements is not known. In this case, you'll have to scan through each element of the array to find the element with the specified property. 

The Algorithm can be written like this:
* Given an Array **Arr** and Item to be found **data**.  

* Check the first element. If it is equal to data, return position of the first element. Else check for the next element.

* Check until the last element is compared.

* If data not found in the array, return -1.
*This type of linear Search is called Unordered Linear Search*

```java
public int unorderedLinearSearch(int[] Arr, int data)
{
    for(int i=0; i<Arr.length; i++){
        if (Arr[i] == data)
            return i;
} 
    return -1;
}

```
Time Complexity: O(n), in the worst case we scan the complete array.
Space Complexity: O(1)

Now, if the array Arr is sorted, i.e. we know the order of elements, we can perform the search as follows:

*This case is called Ordered Linear Search*

```java
public int orderedLinearSearch(int[] Arr, int data)
{
    for(int i=0; i<Arr.length; i++){
        if (Arr[i] == data)
            return i;
        else if(Arr[i] > data)
             return -1;
} 
    return -1;
}

```

We can further optimize the time complexity for the cases when *data* is:
* at the last position in the array from O(n) to O(1) or,
* not present in the array, from O(n) to O(n/2)
by checking elements from left and right positions. 

```java
public int optimiseLinearSearch(int[] Arr, int data)
{
    int left = 0; 
    int length = Arr.length; 
    int right = length - 1; 
    int position = -1; 
  
    for (left = 0; left <= right;){

         if (Arr[left] == search_Element)  
            { 
                position = left; 
                System.out.println(position); 
                break; 
            } 
        
         if (Arr[right] == search_Element)  
            { 
                position = right; 
                System.out.println(position); 
                break; 
            } 
              
            left++; 
            right--; 
     } 
        if (position == -1) 
            System.out.println("data not found"); 
    } 
}

```

Congratulations! Now you know what Searching Algorithms are and how the Linear Search algorithm is implemented. 

In the next blog, we'll be looking at a few more concepts of Data Structures and Algorithms!

Connect with me
[Twitter](https://www.twitter.com/shivikapriya)
[LinkedIn](www.linkedin.com/in/priyasrivastava730
)

Thank You for Reading!:smiley: