Searching Algorithms in Arrays

When you need to find a particular value in an array you apply searching algorithms. There are two search algorithms for an Array:-

• Linear Search

• Binary Search

Linear Search

It is an algorithm for searching in an array by traversing the whole array. If we find the target element we return that element, if we don't, we return -1. To traverse the array we just use a for loop and in each iteration, we compare the value of the array to the target element.

This algorithm is not efficient enough to search for an element. It gives us a time complexity of O(n). Hence we use a better and more efficient algorithm which will yield a better time complexity.

Binary Search

This is a more efficient algorithm for searching in an array. It works on the principle of taking three-pointers start, middle and end. As the pointers' names suggest we put them in their respective positions and run a check if the middle element is the target element or if the target is on the left of the middle or the right, based on the answer we reduce our search space to that side. If we find the element we return it, but if we do not, we keep repeating this process until the search space reduces to one element and returns -1.

You can make an analogy of this algorithm by finding a word in a dictionary. We know a word starts with some letter, we directly open that section of the dictionary where the words from that letters start, hence reducing our search space.

public class BinarySearch{
    static int search(int[] a, int target){
        int start = 0;
        int end = a.length-1;
        while(start<=end){
            int mid = start + (end-start)/2;
            if(target==a[mid]){
                return mid;
            }
            else if(target>a[mid]){
                start = mid+1;
            }
            else{
                end = mid -1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7};
        int target = 3;
        System.out.println(search(arr,target));
    }
}

The time complexity of this algorithm is O(logn) and the space complexity is O(1).

This is a way better and more efficient algorithm for searching if we consider an array with million elements, it will take a million comparisons in the case of linear search but the same thing did with binary search it's taking 20 comparisons only.

Note: Binary Search is only applicable for sorted arrays.

Now we will do some questions on Binary Search.