Searching is a very common action in code. Just imagine an e-commerce website where you are looking for desired items for which you have made a search on their website. Now, just imagine how you would feel if it took forever to load your result and kept showing you a loading bar, which would be really annoying as a user. Here comes the importance of efficient searching algorithms to fasten the searching process. In today’s article, we will be covering two of the most commonly used search algorithms in coding.

Linear Search

As a programmer, you may have used this algorithm a few times without truly realizing that it is an algorithm. Yes, and the name of the algorithm is Linear Search, which is the simplest searching technique where we check every single element in the data structure until the searched element is found. If, after checking all the elements, the searched element is not found, then we come to the conclusion that it does not exist in the data structure.

This algorithm is not widely used for searching techniques because it is not a good approach to check every single element, which slows down your entire code, making the worst-case time complexity of this algorithm O(n). But unlike binary search, linear search can be implemented in both sorted and unsorted arrays.

int linear_search(int *array, int size, int user_search){
    for (int i = 0; i < size; i++)
    {
        if (array[i] == user_search)
        {
            return i;
        }
    }
    return -1;
};

In the above code, we are implementing linear search and finding the searched element and then returning its index. If the element doesn’t exist, we return -1 from the function, which is a standard in code to let the main function handle depending on the linear search function’s return.

Binary Search

Binary search is an efficient searching technique on sorted arrays that starts by accessing the middle element of the array. If the searched element is greater than the middle element, then we continue to search on the right side of the array from the middle element, as it is obvious that the searched element will be on the right side since the searched element is greater than the middle element and the array is sorted too. If the searched element is less than the middle element, then we continue searching on the left side. Now, the question that comes to our mind is how long we will continue this process. We continue the process of searching until the middle element is equal to the searched element, and then if it’s equal to the middle element, we return the index of the middle element. But what if the element does not exist in the array? Keeping that case in mind, we only continue our search while the lower bound is less than or equal to the upper bound. The lower bound is the lower index of the array, and the upper bound is the highest index of the currently searched array.

int binarySearch(int array[], int user_search, int low, int high){
    if (low <= high)
    {
        int mid = (low + high) / 2;        if (user_search == array[mid]){
            return mid;
        }        else if (user_search > array[mid]){
            return binarySearch(array, user_search, mid + 1, high);
        }        else{
            return binarySearch(array, user_search, low, mid - 1);
        }
    }
    else
    {
        return -1;
    }
};

In the above code, we are using a recursive method to do the search. The binary search function has four arguments: the array where we have to do our search (array), the element that we have to search (user_search), the lowest index of the array that has been sent (low), and finally, the highest index of the array (high). When the function is called from the main function, the low index will always be zero, and the high index will be the number that comes after deducting one from the array size, which gives the last index of the array.

Here we are checking at the beginning whether the low index is less than or equal to the high index; this is because it decides whether the searched element exists or not. Then we deduce the mid from the lower and higher indexes, and we set a base case for our recursive function. That is, if the middle element of the searching part of the array is equal to the searched element, then we have our answer, which we return. Otherwise, we do two checks: whether the searched element is greater or less than the middle element of the searching part of the array. If the searched element is greater, then we do a recursive call, but we change our lower index to mid + 1, which lets the function know in which part of the array to continue searching. Similarly, if the searched element is less, we do a recursive call and change our higher index to mid – 1. In other words, changing the low and high index in recursive calls allows us to trim the array and make it shorter so that we continue our search only in the part where we are closer to the result.

Binary Search is a fast search algorithm with a worst-case time complexity of O(log n). It is much more efficient than linear search. However, there are certain limitations to the Binary Search algorithm. Firstly, we can only use this algorithm with sorted arrays. Moreover, binary search doesn’t work on arrays with duplicate elements.

Happy Coding👨‍💻

Categorized in:

DSA,