2 Most important search algorithm for searching value in data structure

The Search algorithm is all about finding a value in data structure in Array, LinkedList, ..

In this article we will talk about Linear search and Binary search.

Linear Search Algorithm:

For this type of search, we just increment the index by one in a linear fashion, from the beginning of the array to the end of the array.

if you reach the end and you did not find the item you are looking for,that means the array doesn’t contain this value.

Example of implementation:

public class Main {

    public static void main(String[] args) {

        int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };

        System.out.println(linearSearch(intArray, -15));
        System.out.println(linearSearch(intArray, 1));
        System.out.println(linearSearch(intArray, -22));

    }

    public static int linearSearch(int[] input, int value) {

        for ( int i = 0; i < input.length; i++) {

            if (input[i] == value){
                return i;
            }
        }

        return -1;
    }
}

It’s time complexity is O(n),because in the worst case,the value we are searching for is at the end of the array, which means we are going to take n steps to that last item.

Binary Search:

It is an efficient algorithm for finding an item from a sorted list of items.

It’s steps :

1. Chooses the element in the middle of the array and compares it against the search value

2. If element is equal to the value, we’re done

3. If element is greater than the value, search the left half of the array

4. If the element is less than the value, search the right half of the array.

Example of implementation,in iterative and recursive methods:

public static void main(String[] args) {

        int[] intArray = { -22, -15, 1, 7, 20, 35, 55};
//
//        System.out.println(iterativeBinarySearch(intArray, -15));
//        System.out.println(iterativeBinarySearch(intArray, 1));
//        System.out.println(iterativeBinarySearch(intArray, 0));;


        System.out.println(recursiveBinarySearch(intArray, -15));
        System.out.println(recursiveBinarySearch(intArray, 1));
        System.out.println(recursiveBinarySearch(intArray, 0));;

    }

    public static int iterativeBinarySearch(int[] input, int value) {

        int start = 0;
        int end = input.length;

        while(start < end) {

            int midPoint = (start + end) / 2;
            System.out.println("MidPoint -> " + midPoint);

            if (input[midPoint] == value) {
                return midPoint;
            }
            else if (input[midPoint] < value) {
                start = midPoint + 1;

            } else {
                end = midPoint;
            }
        }

        return -1;
    }

    public static int recursiveBinarySearch(int[] input, int value) {
        return recursiveBinarySearch(input, 0, input.length, value);
    }

    public static int recursiveBinarySearch(int[] input, int start, int end, int value) {

        if (start >= end) {
            return -1;
        }

        int midPoint = (start + end) / 2;
        System.out.println("MidPoint -> " + midPoint);

        if (input[midPoint] == value) {
            return midPoint;
        }
        else if (input[midPoint] < value) {
            return recursiveBinarySearch(input,midPoint + 1, end, value );

        } else {
            return recursiveBinarySearch(input,start, midPoint, value );
        }
    }
}

It’s time complexity is O(logn), it keeps dividing the array in half.

At some point, there will be only one element in the partition you’re checking, but it doesn’t have to get to that point.

As a conclusion,for binary Search implementation, it’s better for performance to use iterative method instead of recursive one.