Searching Algorithms in Detail

Hello Guys👋 Hope you are doing great !! Welcome to the first article of the Data Structures and Algorithms series, in which we'll go over all of the major concepts so you can master DSA.

In this article, We will discuss about Searching Algorithms.

We will discuss the Main Idea, Algorithm, Implementation, Complexity Analysis, Advantages and DisAdvantages of each one. 🧠

Without Further Ado, Let's get started 👍!!

Introduction

Searching is the process of finding a specific element in a collection of elements. If the element is found in the collection, the process is considered successful, and it returns the location of that element. Otherwise, it deems the search unsuccessful.

Based on the type of search operation, searching algorithms are classified into two categories.

1. Sequential Search: In this type, the collection is traversed sequentially, and every element is checked. For Example, Linear Search.

2. Interval Search: These algorithms are used to search in sorted collections. These are much more efficient than Linear Search because they repeatedly target the center of the search structure and divide the search space in half. For Example, Binary Search.

1️⃣ Linear Search

Main Idea: Traversing the list of items from start to end and exploring all the element's properties on the way.

Example: You have to find and print indices of all the elements whose value is x in the array of size n.

for each element in the array {
    if(current element == x)
        print(index)

Complexity Analysiss

Worst-Case: This occurs when the element we are finding is present at the end of the array or not present in the given array. In this case, we have to traverse the entire array. The worst-case time complexity of the linear search is O(n).

Average Case: The average case time complexity is Θ(n).

Best Case: This occurs when the element we are finding is at the first position of the array. The best-case time complexity of the linear search is Ω(1).

Space Complexity: As it does not need any extra space, Space Complexity is O(1)

2️⃣ Binary Search

Main Idea: Dividing the array into two halves and throwing away one instance of it based on a particular condition. Binary Search only works on sorted collections.

Binary Search follows the divide and conquer approach in which the list is divided into two halves, and the item is compared with the middle element of the list. If the match is found, then the middle element's location is returned. Otherwise, we search into either of the halves depending upon the result produced through the match.

Algorithm

1. Compare x with the middle element
2. If middle element == x: return middle index
3. Else if x > middle element: x can only lie in the right half of the subarray after the middle element, so we search in the right subarray.
4. Else (x < middle element): x can only lie in the left half of the subarray before the middle element, so we search in the left subarray.

Implementation (PseudoCode)

Iterative

function binarySearch(arr, n, target) 
    left = 0
    right = n-1
    while(left <= right)
        mid = low + (high - low)/2
        if(target == arr[mid])
            return mid
        else if(target < arr[mid])
            high = mid - 1
        else 
            low = mid + 1
    return -1

Recursive

function binarySearch(arr, n, target, left, right) 
    if(left > right)
        return -1
    mid = low + (high - low)/2
    if(target < arr[mid])
        return binarySearch(arr, n, target, left, mid-1)
    else 
        return binarySearch(arr, n, target, mid+1, right)
return -1

Complexity Analysis

The time complexity of Binary Search can be written as:

T(n) = T(n/2) + c

The above recurrence can be solved either using the Recurrence Tree method or the Master method. It falls in case II of the Master Method, and the solution of the recurrence is Theta(Logn).

Worst-Case: This occurs when we have to keep reducing the search space till it has only one element. The worst-case time complexity of Binary search is O(logn).

Average Case: The average case time complexity is Θ(logn).

Best Case: This occurs when the element to search is found in the first comparison, i.e., when the first, middle element itself is the element to be searched. The best-case time complexity of Binary search is Ω(1).

Space Complexity:

• Iterative Implementation - O(1)
• Recursive implementation - O(logn) - recursion call stack space

Advantages

1. It is fast and easy to Implement
2. It doesn't require any extra space
3. This reduces the time complexity to a greater extent

Dis Advantages

1. It can only be applied to monotonic problems (sorted collections)
2. It can only be used in data structures that allow direct access to the elements (ex: We cannot use Binary Search on Linked Lists)

🖐☝Conclusion

Finally, In this article we learned about Linear Search and Binary Search Algorithms.

What's Next ⏭?

Thank you for reading so far🙏. I hope you enjoyed following it and got a clear idea on Linear Search and Binary Search. Now open you favourite code editor and start implementing these algorithms in the language you are comfortable with💻.

And also, practise some problems on Binary Search from here.

In the coming parts, we will discuss the Sorting Algorithms in detail !! So Stay Tuned👀👀!!!!

Do share your valuable suggestions and your honest feedback. If you have any comments, questions, or concerns, Do comment them and I am more than happy to take them💬.

Happy Learning 😊👍!!