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

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

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

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.

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 LinkedIn

Thank You for Reading!😊

Data Structure and Algorithms: Linear Search

What is Searching?

But why do we need Searching?

What is Linear Search?