Blog Image

Searching Algorithms  

In many real-time use cases searching an element in the array/list is the common functionality. How the searching algorithm is implemented is given as part of this blog. The working examples of linear and binary search algorithm are described.

The searching algorithm is the process that helps a programmer to find whether required value or element is present in the array/list or not.
The standard searching techniques that are being followed in a data structure is listed below:

  •  Linear Search or Sequential Search
  •  Binary Search

Linear Search
The linear search is the basic searching algorithm where the required value or element is being searched in a sequential manner. The linear search algorithm takes the required value and compares that value with all the elements in the array/list. If the element in array/list matches with the required value then it returns the index otherwise it returns -1. Linear search is preferable when our array/list contains less number of elements.

The program for the linear search is given as follows:

public class LinearSearchDemo {
    public static void main(String[] args) {
        int array[] = { 21, 12, 54, 16, 1, 5, 40, 97 };
        int target = 40;
        int result = search(array, target);
        if (result != -1) {
            System.out.println("the target value found...");
        } else {
            System.out.println("the target value not found...");
        }
    }

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


The output of the above program is :

the target value found...


As we know, the linear search will compare the target value with every element in the array/list. If the list size is large then it not recommends to use linear search.


Binary Search
When it comes to the binary search it is mandatory for the array/list must be already sorted. In binary search algorithm, we first take the required value to search and compare that value with the middle element in the array/list. If the required value and middle element value matches then we return the value.
If the middle element value is greater than the required value then the required value has to be search in a lower half and if the middle element value is smaller than the required value then the required value has to be search in upper half. This procedure has to be repeat until we get the matching value for required value. It is recommended to use binary search when there are large number of elements in array/list.

The program for the binary search is given as follows:

public class BinarySearchDemo {
    public static void main(String[] args) {
        int array[] = { 1, 5, 12, 16, 21, 40, 54, 97 };
        int target = 54;
        int result = search(array, target, 0, array.length - 1);
        System.out.println(array[result]+ " is at index "+result+" in the array");
    }

    public static int search(int array[], int target, int start, int end) {
        int middle = (int) Math.floor((start + end) / 2);
        int value = array[middle];

        if (value > target) {
            return search(array, target, start, middle - 1);
        }
        if (value < target) {
            return search(array, target, middle + 1, end);
        }
        return middle;
    }
}


The output of the above program is:

54 is at index 6 in the array


In the above program, we are first comparing the middle number of the list, with the target, if it matches we return the middle. If it doesn't, we see whether the middle number is greater than or smaller than the target.
If the Middle number is greater than the Target, we start the binary search again, but this time on the left half of the list, that is from the start of the list to the middle, not beyond that.
If the Middle number is smaller than the Target, we start the binary search again, but on the right half of the list, that is from the middle of the list to the end of the list.

You can download the above program from the below attachment.

About author

User Image
AdityaT

I am a software developer. I am working working on jdk , jee technologies. I am working on Spring Framework as well. I am passionate about learning java technologies like Web Services and Restful Services.

0

-Comments

Be the first person to write a comment for this Blog
Load More

No More Comments

Leave a Comment

Your comment has been posted and will appear soon.