Mastering Search Algorithms: Linear Search, Binary Search, and Beyond

In my journey to mastering Data Structures and Algorithms (DSA), searching has become one of the most fundamental topics to understand. Through Kunal Kushwaha’s detailed DSA playlist, I dove deep into linear and binary search algorithms, including the application of binary search in 2D arrays. This blog is a summary of what I have learned, what I have gained insight into, and what problems I have solved along the way.

Linear Search :

Linear search is one of the most basic and straightforward search algorithms. It involves going through each element in an array one by one until the target element is found or the array ends. While this approach is simple to implement, it’s not the most efficient, especially when working with large datasets.

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

When to use Linear Search :

Linear search is best used for small, unsorted arrays. Although it has a time complexity of O(n), its simplicity makes it a good first choice for beginners to understand the search's core idea.

In Kunal’s course, I learned how linear search works and how it performs in both small and large arrays. The inefficiency in larger datasets made me curious about more optimized approaches, which led to …

Binary Search

Binary search is a much more efficient algorithm compared to linear search, but it comes with a condition—the array must be sorted. The binary search follows the divide-and-conquer strategy, which splits the array into halves, reducing the search space in each iteration. This makes its time complexity O(log n), which is significantly better than O(n).

private int searchBinary(int[] arr) {
    int start = 0;
    int end = arr.length - 1;

    while (start <= end) {

        int mid = (start + end) / 2;
        if (arr[mid] > arr[mid+1]) {
            end = mid;
        } else if (arr[mid] < arr[mid+1]) {
            start = mid + 1;
        }
        else if (start == end){
            return mid;
        }
    }
    return -1;
}

Key Insights from Kunal’s Course about Binary Search

Here’s how binary search works:

1. If the middle element matches the target, return its index.

2. If the middle element is larger than the target, search the left half.

3. If the middle element is smaller, search the right half.

4. Repeat until the target is found or the array is fully searched.

Kunal’s 4-hour deep dive into binary search helped me understand every minute detail. I realized that while the concept is simple, implementing binary search correctly requires careful consideration of boundary conditions, especially when calculating the mid-point of the array to avoid integer overflow.

Binary Search in 2D Arrays

Binary search can also be applied to 2D arrays, but it works best in matrices that are row-wise and column-wise sorted. The logic is similar to the 1D binary search, except we treat the 2D array as a linear list by mapping the row and column indices to a 1D representation.

Why 2D Binary Search is Important

This was a particularly fascinating section of the course because it showed how adaptable binary search is across different data structures. Applying the divide-and-conquer strategy in two dimensions was challenging at first but incredibly rewarding when I solved related problems on LeetCode.

LeetCode Problems Solved

To strengthen my understanding, I solved various LeetCode problems that involve linear and binary search. These problems helped me grasp the nuances of each approach and how they can be applied to real coding challenges:

• Search in Rotated Sorted Array (medium)

• Find the First and Last Position Of the Element In a Sorted Array (medium)

• Peak Index In Mountain Array (medium)

Code Repository

The code I wrote while learning and practicing these search algorithms is available in my GitHub repository. Feel free to check it out, play around with the code, and maybe even contribute!

Here’s the link to my repository: GitHub Repo

Conclusion

Searching algorithms are a core part of DSA, and understanding the difference between brute-force approaches like linear search and optimized solutions like binary search is crucial for any aspiring software engineer. Learning binary search in 2D arrays was particularly rewarding, as it introduced me to more complex ways to think about searching in larger datasets.

In my next blog, I’ll dive into sorting algorithms like bubble sort, selection sort, and more. Stay tuned!