Search

Consider, you want to find if a number exist between 1-1000 in a given list. Finding it manually will be difficult and so we leave it to computer to do the work.

In Java, you can make a program which performs this task easily. There are two types of search:

  • Linear Search
  • Binary Search

Linear Search:

This search goes in a sequence. It will check from start and terminate if the given element is found. So, it’s also called sequential search.

Q. Make a list of 10 numbers. Give a number to be found. Check whether the given number exist in the list or not using linear search.

import java.util.Scanner;
public class linear_search
{
    public static void main()
    {
        System.out.println(“Enter 10 numbers in the list”);
        Scanner in=new Scanner(System.in);
        int arr[]=new int[10],inc=0;
        for(int i=0;i<10;i++)
        arr[i]=in.nextInt();
        System.out.println(“Enter a number to be found”);
        int num=in.nextInt();
        for(int i=0;i<10;i++)
        {
            if(arr[i]==num)
            {
                inc++;
                break;
            }
        }
        if(inc==0)
        System.out.println(“Not found”);
        else
        System.out.println(“Found”);
    }
}

Binary Search:

This search is faster than linear search. In this search, array is split into half. Searching takes place in either half of the array by further dividing it into halves. 

The array have to be sorted before the search.

It always compares the element to be searched with the middle element. If the middle element is smaller then, the search is carried out in upper half, otherwise the search continues in the lower half.

 The middle element of either half is compared with the search item. This process is repeated till the search terminates.

Suppose, you want to search 20 in the given array containing elements in sorted order as shown:

  1. First= 0th , Last= 6th, Mid= (First+ Last)/2 = 3rd. As the element to be found is less than middle element, the search takes place in the lower half.

       2. First= 0th, Mid=1st, Last=2nd

Now, 1st position in the array is the middle position and is checked for 20. As the element in 1st position is 20 the search is ‘successful’ and is terminated.

What if array contained even number of elements:

Let’s take the same example. We have to find 20 in the given six elements.

  1. First=0th,  Last= 5th, Mid=(First+ Last)/2 = 2nd. That is, if Mid is 2.5, then the value comes down to 2.

First=0th,  Mid= 1st, Last= 2nd. 

Now, 1st position in the array is the middle position and is checked for 20. As the element in 1st position  is 20 the search is ‘successful’ and is terminated.

Q. Make a list of 10 numbers. Give a number to be found. Check whether the given number exist in the list or not using binary search.

import java.util.Scanner;
public class linear_search
{
    public static void main()
    {
        System.out.println(“Enter 10 numbers in the list”);
        Scanner in=new Scanner(System.in);
        int arr[]=new int[10],first=0, last=9,mid=0;
        for(int i=0;i<10;i++)
        arr[i]=in.nextInt();
        System.out.println(“Enter a number to be found”);
        int num=in.nextInt();
        while(first<=last)
        {

            mid=(first+last)/2;
            if(arr[mid]<num)
            first=mid+1;
                if(arr[mid]>num)
                last=mid-1;
            if(arr[mid]==num)
            {
                inc=1;
                break;
            }
        if(inc==1)
        System.out.println(“Found”);
        else
        System.out.println(“Not Found”);
    }
}

Conclusion:

Now you know how to use linear and binary search in your programs. For binary search, your array needs to be sorted. But it is system friendly also. 

When you have a large list having 1000 elements, using linear search will consume high electrical power if the element to be found is almost at the end. So, both searches are needed according to different situations.

If the list is small ( 10 to 15 elements) then linear search is a better option.