**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};**

** **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.

Now 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**