Search Algorithms: Linear & Binary

Searching algorithms are an essential part of computer science and programming. They allow us to efficiently find specific values in a collection of data. Two popular search algorithms are linear search and binary search.

Linear search, also known as a sequential search, is the simplest searching algorithm. It checks every element in a list or array until the desired value is found or the end of the list is reached. Here's a simple implementation of linear search in Java:

public static int linearSearch(int[] arr, int val) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == val) {
            return i;
        }
    }
    return -1;  // if the value is not found
}
// Example usage:
int[] myArray = {2, 4, 6, 8, 10};
int result = linearSearch(myArray, 8);
System.out.println(result);  // output: 3

In the above code example the array given is an array of length 5. We start the search from the 0th Index of the array containing the number 2 and we keep searching one by one till the last index of array holding the number 10. If the compiler finds the number we are searching for then it will return true.

To understand binary search with real-life examples, imagine you are trying to find a particular book in a library. The books are arranged in alphabetical order by title, and you know the book you want starts with the letter "M".

Using a linear search, you would start at the beginning of the shelf and look at each book until you find the one you want. This would take a long time and be very inefficient.

However, with a binary search, you can quickly find the book by dividing the shelf in half and determining which half of the shelf your desired book is in. Then, you repeat the process with the half of the shelf that contains the book until you find the book you want. This is much faster and more efficient than a linear search.

Binary search is a more efficient searching algorithm that works on a sorted list or array. It repeatedly divides the search interval in half until the desired value is found or the interval is empty. Here's a simple implementation of binary search in Java:

public static int binarySearch(int[] arr, int val) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == val) {
            return mid;
        } else if (arr[mid] < val) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;  // if the value is not found
}
// Example usage:
int[] myArray = {2, 4, 6, 8, 10};
int result = binarySearch(myArray, 8);
System.out.println(result);  // output: 3

Conclusion

In conclusion, searching algorithms are an essential part of computer science and programming, and understanding them is crucial for efficient searching of data. Both linear search and binary search are widely used searching algorithms that have their unique advantages and disadvantages.

In general, if you are searching for a value in a small dataset or an unsorted list, linear search is a suitable algorithm to use. If you are searching for a value in a large dataset or a sorted list, binary search is a better choice as it can significantly reduce the search time.

Ultimately, the choice of which algorithm to use depends on the specific requirements of your task. By understanding the strengths and weaknesses of each algorithm, you can choose the most appropriate searching algorithm for your specific use case and improve the efficiency of your search.