codedamn

What is the best searching algorithm? Explained

What is the best searching algorithm? Explained

You might have tried to search for something on your electronic devices be it searching for any video on youtube or searching for any query on Google. Do you ever wondered how can Platforms can search billions of data within a matter of seconds, What Searching algorithms do they use to search this tremendously fast on their platform??

Well, today we’re gonna talk about some of those algorithms in this article to let you a basic knowledge about the best searching algorithm to search for in any list, arrays, files, or maybe Operating System or whatever.

A searching algorithm means that a device can make use of a pattern to search for any defined term in the given set of data in the fastest way possible. Any of the search operations will only return 2 possible outcomes either it’ll be Positive or negative ( either the element is found or not found ). There are mainly two types of Searching algorithms:

  • Sequential Search
  • Interval Search

In all of the searching algorithms, there are many of them we’re gonna talk about 3 of them:

  • Linear Search
  • Binary Search
  • Jump Search

In Sequential Search the program traverses the data provided one by one at every possible data available in the given set of data, i.e. it’ll traverse every element of the data even by knowing that it’s not the element we’re looking for. The most famous use case for this search is Linear Search.

This type of searching Algorithm checks each element in the given data until the element is found or until all the elements of the data are traversed. In the worse case, all the elements have been traversed which will be O(n), where n = length of the given data.

Linear Search is rarely practical because of other algorithms like Binary Search and Hashtables which allows significantly faster searching when compared with linear search.

The efficiency of a Search algorithm is compared with the number of comparisons it makes in the given data, to which Linear Search makes n comparisons.

Code

// Java Code for Linear Search

public static int[] linearSearchAlgo(int[] arr, int key){  
    int[] returnArray = {0, 0};
    for(int i=0;i<arr.length;i++){    
        if(arr[i] == key){    
            returnArray[0] = 1;
            returnArray[1] = i;
            return returnArray;
        }    
    }    
    returnArray[0] = 0;
    returnArray[1] = -1;
    return returnArray;    
} 

public static void main(String[] args){
    int[] arrayData = {10,20,30,40,50};
    int key = 20;
    int[] index = {0, 0};
    index = linearSearchAlgo(arrayData, key);
    if (index[0] == 1){
        System.out.println("Element is Found at Poisition : "+index[1]);
    } else {
        System.out.println("Element not present in the Array");
    }
}

Code language: HTML, XML (xml)

The time complexity for this search is O(n).

This searching algorithm is specially designed to search for a given element from the sorted data, it’s not efficient on data that is not sorted. These Search algorithms are much more efficient and faster than Sequential Search algorithms. The most famous use case for this type of algorithm is Binary Search.

It is an Interval Search algorithm, this algorithm works on the principle of divide and conquer. It is used to find a particular element from a sorted array/list. It is considered the best searching algorithm due to its fastest speed to search ( though it has a special condition that the array should be sorted ).

It is also known as Half-Interval search or Logarithmic search.

Binary search divides the given sorted array and checks whether the element is available in the first half or the second half. Then it repeats the process until the element is found or the elements run out. Binary Search starts from half of the array which reduces the time to search significantly.

The time complexity of Binary Search is always O(logn).

Code

int binarySearch(int arr[], int l, int r, int x)
    {
        if (r >= l) {
            int mid = l + (r - l) / 2;
            if (arr[mid] == x)
                return mid;
            if (arr[mid] > x)
                return binarySearch(arr, l, mid - 1, x);
            return binarySearch(arr, mid + 1, r, x);
        }
        return -1;
    }

    public static void main(String args[])
    {
        BinarySearch ob = new BinarySearch();
        int arr[] = { 2, 3, 4, 10, 40 };
        int n = arr.length;
        int x = 10;
        int result = ob.binarySearch(arr, 0, n - 1, x);
        if (result == -1)
            System.out.println("Element not present");
        else
            System.out.println("Element found at index "
                               + result);
    }

Code language: JavaScript (javascript)

Jump search is another example of Interval Search in which some elements are skipped rather than checking all of the elements in the given array. This also requires a special condition which is the same as Binary Search Given Array should be sorted. The basic idea is to check fewer elements by jumping over some elements in fixed steps.

Performance comparison between Linear Search, Binary Search, and Jump Search

Linear Search < Jump Search < Binary Search

Code

public static int jumpSearch(int[] arr, int x){
        int n = arr.length;
        int step = (int)Math.floor(Math.sqrt(n));
        int prev = 0;
        while (arr[Math.min(step, n)-1] < x)
        {
            prev = step;
            step += (int)Math.floor(Math.sqrt(n));
            if (prev >= n)
                return -1;
        }
        while (arr[prev] < x)
        {
            prev++;
            if (prev == Math.min(step, n))
                return -1;
        }
        if (arr[prev] == x)
            return prev;
        return -1;
    }

    public static void main(String [ ] args){
        int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21,
                    34, 55, 89, 144, 233, 377, 610};
        int x = 55;
        int index = jumpSearch(arr, x);
        System.out.println("\nNumber " + x +
                            " is at index " + index);
    }
Code language: JavaScript (javascript)

Time Complexity Analysis

Best Case: The Best case for Linear Search can be only if the element is found at the first index- only. So if ever that array appeared then time complexity will be O(1)

Average Case: The Average case for Linear Search to ever appear is if only the element to be searched for appears in the middle of the array. In that case, number of comparisons will be N/2 and the time complexity will be O(N) ( The constant being ignored ).

Worst Case: The Worst case for any Linear Search Algorithm can be if the element is not in the array. If the element is not found in the array then the program will have already traversed n times for nothing. In that case, the time complexity will be O(N).

The Best Case occurs when the target element is the middle element of the array. The number of comparisons, in this case, is 1. So, the time complexity is O(1).

Best Case: Best Case for any of these algorithms is when the element is found in the middle of the array. The number of Comparision, in this case, is 1. So, the time complexity is O(1).

Average Case: Average Case for any of this Algorithm is when the element is found somewhere in the middle. So, the time complexity is O(logN).

Worst Case: Worst Case for any of these algorithms is when the element is not found, in this case, no comparisons will be log n + 1. So, the time complexity is O(logN).

No. of comparisons made in any Jump Search Algorithm n/m times. Thus the time complexity for Jump Search is O(\sqrt N).

Conclusion

In this article, we discussed some of the best searching algorithms. We also did a time complexity analysis to search for in-depth code implementation. We recommend you to go through Binary Search as it’s the most important topic with the Interview in mind.

We recommend you take up Python Course if you want to learn all these algorithms in the easiest way.

Thanks for reading
Happy Hacking

Sharing is caring

Did you like what Aman wrote? Thank them for their work by sharing it on social media.

0/10000

No comments so far