Searching Arrays in Java   

Searching is a basic operation in Java  whcih is processed to determine wheather a given item is present in the array or not. Suppose, for example, we had an array of records of cars and we wanted to search it to see if it had a record for a car with a particular registration number. In this case, the registration number is used as a key to retrieve a complete object containing more complex data.

In order to concentrate on the basics of searching an array, just as we looked at sorting arrays of integers, so we shall look at searching an array of integers to see of one of its cells contains a particular integer. This can be done in two ways :

1.Linear Searching 
2.Binary Searching

Linear Searching :

Check this program which demonstrates Linear Searching

import java.util.*;//importing Scanner class into the program
class LinearSearching//Declaration of class as LinearSearching
{//class opens
static void main()//declaration of the function main()
{//function main() opens
Scanner sc=new Scanner(System.in);//Declaring a new variable in Scanner Class to input data
int ar[]={2,5,1,3,9};//Initialising an array ar with five elements
System.out.print(“Enter the number to be searched : “);//Print Statement to direct the user to input a number
int s=sc.nextInt() //Input Statement of int-data type in Scanner Class
for(int i=0;i<ar.length;i++) //loop iterating when i value is between 0 and length of the array
{  //for loop starts
if(ar[i]==s)  //Conditional Statement checking if the input value equals with numbers in the array
System.out.println(“The Element is present at “+i+”th position of the array”);
 //Print Statement to print the position of the number if it is present in the array
}//End of for loop
}//function main()  closes
}//class closes

 

Linear Searching is one of the simplest teachnique in searching for an item in an array.It is very easy to understand and doesn’t need any exceptional skills to understand this program. However in this method, the elements are not required to be in specific (ascending/descending) order.They can be in unarranged order.

Linear Searching is a simple approach.This method is also known as Sequential Search as the searching starts from the beginning of the array, checking if the required number equals to the number in that element/index .This operation continues till the end of the array checking all the elements. If the number is present, it notes the index number and dsiplays it.

Note : As I am demonstatring this program with an integer array ,it’s not true that the searching is only for integer arrays . The searching can also be used in the case of other type of arrays also.

Now in the Present Example,we have initialised the array as ar[]={2,5,1,3,9};
Let us assume that the user had entered the value ‘1’ to be searchind in the array which is taken into variable s.
The for loop block in the program is : for(int i=0;i<ar.length;i++);
{
if(ar[i]==s)
System.out.println(“The Element is present at “+i+”th position of the array”);
}
If you are not aware,Let me tell you In Java Programming the index numbers of the elements in an array starts from 0th value.
For Example if an integer array has 8 numbers stored in it,the length of the array will be 7.
In the present example ,length is 4 and the function ar.length results the length of the array.

In this for loop ,the first iteration i takes the value i=0
the execution next comes to the if block ,there it checks the statement (ar[i]==s)
Here ar[i] results the ‘i ‘ th element in the array.As the value of i is 0, it results 2 and now checks if 2==1 which is false
So,the execution skips the print statement in if block and the variable in for loop goes for increment.

In the second iterartion,after increment i takes the value  i=1
In the same way, it checks the condition if 5==1 which results false

In the third iteration,after increment i takes the  value i=2
It checks the statement 1==1 which results true and the print statement is executed

Though we have found the number required and the index at which it is present ,the loop executes all its iterations till the end.

Therefore, Linear Searching is very easy but its execution takes a large time than binary search.

Binary Searching :

Check this program which demonstrates Binary Searching

import java.util.*;//importing Scanner Class into the program
class BinarySearching//Declaration of class as BinarySearching
{//class opens
static void main()//declaration of the function main()
{//function main() opens
Scanner sc=new Scanner(System.in); //Declaring a new variable in Scanner Class to input data
int ar[]={2,4,15,29,33,56,87};//Initialising an array ar with seven elements
System.out.print(“Enter the number to be searched : “);//Print Statement to direct the user to input a number
int s=sc.nextInt();//Input Statement of int-data type in Scanner Class
int l=ar.length;//The function stores the length of the array in variable
int first=0;
int last=l;
while(first<=last)//while loop which executes if the given condition is satisfied
{
int mid= (last+first)/2;//to store the middle index number of array
if(ar[mid]==s)//Conditional Statement checking if the input value equals middle number of array
{
System.out.println(“The element is present at “+mid+”th index of array”);
//Print Statement to print the position of the number if it is present in the array
break;//break statement,used to stop the execution and skip out of the loop
}
if(ar[mid]<s)//Conditional Statement checking if the input value greater than middle number of array
first=mid+1;
if(ar[mid]>s)//Conditional Statement checking if the input value lesser than middle number of array
last=mid-1;
}
}
}

Binary search  works only on sorted arrays i.e, elements of the array are to be arranged either in ascending or descending order.
This search executes in minimum possible time. Binary search begins by comparing the middle element of the array with the required value. If the required value matches the middle element, its position in the array is returned. If the required value is less than or greater than the middle element, the search continues in the lower or upper half of the array, respectively, eliminating the other half from consideration.

It takes very much less time than linear searching. In  Linear search, the every element of the array is checked with the condition ,whereas in binary search as we take sorted arrays we can easily search for the required value in less execution.

Binary search compares the middle value to the required value ,
If the middle value is greater than required value, then it searches for the required value in first half of the array
If the middle value is lesser than required value,then it searches for the required value in second half of the array
As the required value may also be present at the middle, so binary search checks that condition too,

Looks like You feel confused,Let me explain you with the example written in the program.
We have initialised the array as  ar[]={2,4,15,29,33,56,87};

arrays
Assume,the user have asked for number 4 to be searched,
The While loop contructed in this program is as : while(first<=last)
{
int mid= (last+first)/2;
if(ar[mid]==s)
{
System.out.println(“The element is present at “+mid+”th index of array”);
break;
}
if(ar[mid]<s)
first=mid+1;
if(ar[mid]>s)
last=mid-1;
}

This while loop iterates if the condition first<=last is satisfied. We have initialised first with 0 value and last with the length of the array i.e, 6 . Since 0<=6, is true ,the execution enters the body of the loop which contains if conditional statements.
In the body of the loop, we have declared variable mid as mid =(first+last) /2 which returns the  middle element of the array.In this iteration the value of mid is mid =(0+6)/2=3.The statement ar[mid] returns the middle element i.e, element at 3 rd index of the array.
Therefore ar[mid]= 29.While executing the conditional statements , the first if condition (ar[mid]==s) is false,so execution skips to next if condition (ar[mid]<s) which is also false.The third if condition (ar[mid]>s) i.e, 29>4 is true.So the statement/body of third if statement is executed. In third if block we have the statement to be executed last=mid-1.So the value of the variable last change to
last=mid-1=3-1=2.
The reason we have changed the value of last variable is ,from the first iteration we came to know that the required value is in the first half of the array(since 4 is less than the middle element of the array 29).So by changing the value of last variable to mid-1, we can perform binary search on the first half of the array.
Now the values of first and last variables are 0 and 2.
arraysNow again,Binary Search technique is performed on the first half of the array.Mid value =(0+2)/2=1.
The condition in the while loop, first<=last i.e, 2<=0 is true,so the the if conditions are checked in the same way.
ar[mid]=ar[1]=4. Therefore the first if condition (ar[mid]==s) is true and the body of this if statement is executed.
It contains a print statement and a break statement.The reason why break statement is used is,in the absence of break statement the while loop results to a infinite loop.Break statement if used  in a loop will terminate the loop and the control resumes to the next statement following  the loop.

Dont at all forget that binary search is only for sorted arrays

So that’s all about Searching Arrays in Java. if you have any doubts or suggestions for us, please feel free to comment below. We will respond immediately!

 

 

 

Watch this tutorial for further more grasp on the method of searching

Share This

Share This

Share this post with your friends!

Subscribe To Our Newsletter and Never Miss an Update!

Subscribe To Our Newsletter and Never Miss an Update!

Leave us your Email ID and we will notify you whenever we release new Videos, Articles or Apps.

You have Successfully Subscribed!