Searching in Array

Linear Search

It is one of the simplest techniques to search a value within an array.

It traverses the array sequentially to locate a given value and that is the reason due to which, it is also known as sequential search.

Now, suppose if we search for 42 in this array, then it will search the array sequentially as shown in the below diagram.

If we search for 32, it is not present in the array, resulting in an unsuccessful search and unsuccessful search is represented by -1.

Here is a Linear Search Related Question

Define a class to search for a value input by the user from the list of values given below. If it is found, display the message, Number exists. Otherwise display the message, Number doesn't exists using linear search technique.

11,25,36,47,58,69,79,92

Answer:

import java.util.Scanner;
class hello
{
    public static void main(String[]args)
    {
        Scanner kbd = new Scanner(System.in);
        int searchnumber;
        int foundindex = -1;
        int list[]={11,25,36,47,58,69,79,92};
        System.out.println("Enter a number to search");
        searchnumber= kbd.nextInt();
        for(int i = 0;i<list.length;i++)
        {
            if(list[i]==searchnumber)
            {
                foundindex = i;
                break;
            }
        }
        if(foundindex>=0)
        {
            System.out.println("Number exists");
        }
        else
        {
            System.out.println("Number doesn't exists");
        }
    }

}

Guide of how code is working

Line 8: Initialized the foundindex variable with a default value of -1 indicating value is not found

Line 11: Accepting the number to search for and stored it to search number
Line 12: Iterates through the array using the length property
Line 14: Checks if searchnumber matches any of elements in array.
Line 16: Assigns the index value to the foundindex variable.
Line 17: If searched value is defected, loop is terminated with break statement.
Line 20: Checks if foundindex variable was assigned any value in loop.
Line 22: Displays the success message.
Line 26: Else, Displays unsuccessful message.

Binary Search

Binary search is another technique which is used to find an element in array by the array needs to be sorted. It is faster than linear search.

Here is an example of an array namely list having 9 elements in it.

Lets imagine that number to be searched = 78

Let us call this number to be searched as searchNumber.

Since we need to divide the sorted array into two halves, we will need three variables:

start - Stores start index of array

end - Stores end index of array

mid - Stores middle value of index

Pass 1:

start = 0

end = 8

mid = (start+end)/2 = (0+8)/2 = 4

searchNumber will be compared to the value at the mid position 4 i.e list[mid]. Now, there are three possibilities:

i. searchNumber is equal to value at list[mid]. In this case, loop will break.

ii.searchNumber is less than the value at list[mid]. In this case, number to be searched exists in first half. Hence, we adjust end variable to one less than mid.

    end = mid-1

iii. searchNumber is greater than the value at list[mid]. In this case, number to be searched exists in second half. Hence, we adjust start variable to one more than mid.

    start = mid+1

Here, searchNumber (i.e 78) is greater than list[mid] (i.e 62) as it can be seen in the above diagram, hence we will adjust the start variable as per point number iii.

The updated value will be:

start = mid+1 (i.e. 4+1 = 5)

Pass 2

start = 5

end = 8

mid = (start+end)/2 = 5+8/2 = 6

searchNumber is again compared with the value at list[mid]. Here, searchNumber is less than value of list[mid]. Hence, we will adjust the end variable as per point number ii.

Now, updated value will be:

end = mid-1 (i.e. 6-1 = 5)

Pass 3

start = 5

end = 5

mid = (start+end)/2 = 5+5/2 = 5

searchNumber is again compared with the value at list[mid]. Here, searchNumber is equal to the value at list[mid]. Hence, search successful.

Here is a Binary Search Related Question

Define a class to search for a value input by the user from the list of values given below. It is is found, display the message, Number exists. Otherwise display the message, Number doesn't exists using Binary search technique.

11,25,36,47,58,69,79,92

Answer:

import java.util.Scanner;

class hello

{

    public static void main(String[]args)

    {

        Scanner kbd = new Scanner(System.in);

        int searchnumber;

        int foundindex = -1;

        int start, end, mid;

        int list[]={11,24,36,47,58,69,79,92};

        System.out.println("Enter a number to search");

        searchnumber= kbd.nextInt();

        start = 0;

        end = list.length-1;

        while(start<=end)

        {

            mid = (start+end)/2;

            if(searchnumber==list[mid])

            {

                foundindex = mid;

                break;

            }

            else if(searchnumber<list[mid])

            {

                end = mid-1;

            }

            else

            {

                start = mid+1;

            }

        }

        if(foundindex>=0)

        {

            System.out.println("Number exists");

        }

        else

        {

            System.out.println("Number doesn't exists");

        }

    }

}

Guide of how code is working

Line 8: Initialized the foundindex variable with a default value of -1 indicating value is not found

Line 12: Accepting the number to search for and stored it to search number
Line 13: Initialized start variable with 1st index i.e 0
Line 14: Initialized end variable with last index i.e length of array-1

Line 15: Loops through until start is less than or equal to end.

Line 17: Calculates value of mid variable i.e. mid index.

Line 18: Checks if searchnumber matches with array element at mid index.

Line 20: Updates foundindex variable with index value at mid location.

Line 21: Stops searching further.

Line 23-25: If searchnumber is present in first half, it adjusts the end variable

Line 29: Else, adjust the start variable.