Array is an interesting topic. Imagine a situation where you
want to input the names of students in your class along with
the roll no and 3 subjects marks. There are 50 boys in your
class. Then how many variables you need? There is no point
in writing a program. Array comes in handy in such a
situation .
An array is a collection of values of same data type. Each element in an array is refered by the array name with the subscript or index.It is enclosed in square bracket [ ], whereas methods use ( ).
Like the normal declaration of variables, we need to declare the array also.
data type array name[];
int marks[];
Memory allocation:
data type array name[]=new datatype[size];
int a[]=new int[10];
How many values you are going to use should be mentioned where it is given size.The common mistake we make here is writing the variable name after new.
int a[]=new a[10]; is wrong
Initializing values
int a[]={10,20,30,40};
The place value of each element is called a subscript or an
index. The index value starts from zero, so the last
element index is one less than the size.
To find the length of an array use length.
int l=a.length;
No brackets after length. It finds the length of the array 'a'
which is 4 and it is stored in a variable l;
To accept 10 values from the user.
Example 1: Blue J method
class ar1
{
public static void main(int a[])
Example 2: Scanner Method
import java.util.*;
class ar1
{
public static void main()
{
int a[]=new int[10];--------------------------1
Scanner s=new Scanner(System.in);
int i,l,s=0;
l=a.length;------------------------------------2
System.out.println("Enter the values");
for(i=0;i<l;i++)------------------------------3
a[i]=s.nextInt();------------------------------4
for(i=0;i<l;i++)
s=s+a[i];-------------------------------------5
System.out.println(a[i]);
}
}
Step 1 : an array a is created ,
Step 2 :finds the Length
Step 3 : index starts from 0 and less than length l
Step 4 : The values are store in a.First value is stored in
a[0], second in a[1] and so on
Step 5: When i=0, a[0] value is added to s, when i=1 ,a[1] is added and so on..
Loop plays an important role in Arrays , whether it is for accepting values or printing it.
Accepting values :
Write the Java statements for the following:
Search
import java.util.*;
class linear{
public static void main()
{
int a[]=new int[10];
Scanner s=new Scanner(System.in);
int i,l,n,flag=0;
l=a.length ;
System.out.println("Enter the values");
for(i=0;i<l;i++)
a[i]=s.nextInt();
System.out.println("Enter the number to be searched");
n=s.nextInt();
for(i=0;i<l;i++)
{
if(a[i]==n)
{
flag=1;
break;
}
}
if(flag==1)
System.out.print(n+"found");
else
System.out.print(n+"not found");
}
}
Initially flag is 0, if the number is found the flag value will change to 1.
Binary Search
This might look little complicated,but if you understand how it works,it is a cake walk.
The prerequisite is that the array elements should be arranged in some order either in ascending or descending.
In the boards generally the question will not ask you to sort
and search in the same program.
The linear search takes more time since it has to check each
and every element sequentially.It is a good idea but not a great one.
So, here in binary search the idea is divide the array and discard whatever not necessary.
Step 1: we are going to divide the array into two parts.
For that we should find the middle value.
Step 2: Compare the number to be searched say 'n' with the middle value say 'm'.If both are same, Bingo.
Step 3: If the n is smaller than m, then you would find n in
the first half ,if the array is arranged in ascending order.Then
you dont want the second part anymore.discard it. So the
length changes after you discard the second part.Lower index
value remains the same that is 0, but upper limit becomes
middle value - 1.Then step 2 will be repeated.
If the n is bigger than m, then you would find n in the second
half ,if the array is arranged in ascending order.Then you
dont want the first part anymore.discard it. So the length
changes after you discard the second part.Upper index value
remains the same, but lower limit becomes middle value +
1.Then step 2 will be repeated.
Example :
The array is
14 , 23, 28, 36, 69, 88
The number to be searched is 23.
Step 1:
Middle value = (lower index +Upper index)/2
= (0+5)/2
= 2.5
Either round off or truncate it. Let us take 3.So the middle value is 36.
Step 2 :
Compare 23 and 3 rd element 36.Both are not same.
Step 3 :
23 is smaller than 36, that means 23 will not be there after 36.
so discard second half, that is elements after 36.Lower index is still 0, and upper index becomes the value before the middle value , i.e 28.
Checking will go on till it finds the value.
If the value to be searched is 88 then,
88 is bigger than 36, therefore 88 will not be in the list
before 36.
so discard first half, that is elements before 36.upper
index remains the same and lower index becomes the
value after the middle value.
Checking will go on till it finds the value. Otherwise it will print the nmber not in the list.
class binary
{
public static void main(int a[],int n)---------------------------1
{
int l,i,mid,place,flag=0;
l=a.length;--------------------------------------------------------2
int low=0,up= l -1;----------------------------------------------3
while(low <= upp)----------------------------------------------4
{
mid = (low+up)/2;------------------------------------------5
if(a[mid]==n)
{
flag=1;------------------------------------------------6
place=mid;--------------------------------------------7
break;-------------------------------------------------8
}
else if(a[mid] < n)-----------------------------------------9
low=mid+1;
else
upp=mid - 1;
}
if(flag==1)
System.out.print(n+"is found at+(place+1));-----------------10
else
System.out.print(n+"is not found ");
}
}
step 1: input the array, number to be searched
step 2: find the length of the array
step 3:initialize the values for lower and upper index. l-1 coz, index starts from 0.
step 4:the loop should continue as long as lower limit is less than upper limit.
step 5:find the middle value.common mistake here is
(a[low]+a[upp])/2
step 6:there is some variable with some intial value so that when we find the number, change that value.If the value is not changed then it means the number is not found,coz you would not have gone to step 6.
step 7: if you want to find exactly where the number occurs in the array,then assign the mid index, not mid value.It is not a[mid].
step 8:Once we found the number,come out. no more searching.
step 9:check the number with middle value , change the low or upper index accordingly.
Isn't that easy.
want to input the names of students in your class along with
the roll no and 3 subjects marks. There are 50 boys in your
class. Then how many variables you need? There is no point
in writing a program. Array comes in handy in such a
situation .
An array is a collection of values of same data type. Each element in an array is refered by the array name with the subscript or index.It is enclosed in square bracket [ ], whereas methods use ( ).
- Declaration
- Memory allocation
- Initialization
Like the normal declaration of variables, we need to declare the array also.
data type array name[];
int marks[];
Memory allocation:
data type array name[]=new datatype[size];
int a[]=new int[10];
How many values you are going to use should be mentioned where it is given size.The common mistake we make here is writing the variable name after new.
int a[]=new a[10]; is wrong
Initializing values
int a[]={10,20,30,40};
The place value of each element is called a subscript or an
index. The index value starts from zero, so the last
element index is one less than the size.
To find the length of an array use length.
int l=a.length;
No brackets after length. It finds the length of the array 'a'
which is 4 and it is stored in a variable l;
To accept 10 values from the user.
Example 1: Blue J method
class ar1
{
public static void main(int a[])
Example 2: Scanner Method
import java.util.*;
class ar1
{
public static void main()
{
int a[]=new int[10];--------------------------1
Scanner s=new Scanner(System.in);
int i,l,s=0;
l=a.length;------------------------------------2
System.out.println("Enter the values");
for(i=0;i<l;i++)------------------------------3
a[i]=s.nextInt();------------------------------4
for(i=0;i<l;i++)
s=s+a[i];-------------------------------------5
System.out.println(a[i]);
}
}
Step 1 : an array a is created ,
Step 2 :finds the Length
Step 3 : index starts from 0 and less than length l
Step 4 : The values are store in a.First value is stored in
a[0], second in a[1] and so on
Step 5: When i=0, a[0] value is added to s, when i=1 ,a[1] is added and so on..
Loop plays an important role in Arrays , whether it is for accepting values or printing it.
Accepting values :
- System.out.println("Enter the values");
for(i=0;i<l;i++)
a[i]=s.nextInt();
Printing :
for(i=0;i<l;i++)
System.out.println(a[i]);
Write the Java statements for the following:
- Declare 5 integers in code.
- Declare to store 10 names.
- Assign the values 10.5, 20.5, 30.5, 40.5 to an array number.
Search
- Linear
- Binary
import java.util.*;
class linear{
public static void main()
{
int a[]=new int[10];
Scanner s=new Scanner(System.in);
int i,l,n,flag=0;
l=a.length ;
System.out.println("Enter the values");
for(i=0;i<l;i++)
a[i]=s.nextInt();
System.out.println("Enter the number to be searched");
n=s.nextInt();
for(i=0;i<l;i++)
{
if(a[i]==n)
{
flag=1;
break;
}
}
if(flag==1)
System.out.print(n+"found");
else
System.out.print(n+"not found");
}
}
Initially flag is 0, if the number is found the flag value will change to 1.
Binary Search
This might look little complicated,but if you understand how it works,it is a cake walk.
The prerequisite is that the array elements should be arranged in some order either in ascending or descending.
In the boards generally the question will not ask you to sort
and search in the same program.
The linear search takes more time since it has to check each
and every element sequentially.It is a good idea but not a great one.
So, here in binary search the idea is divide the array and discard whatever not necessary.
Step 1: we are going to divide the array into two parts.
For that we should find the middle value.
Step 2: Compare the number to be searched say 'n' with the middle value say 'm'.If both are same, Bingo.
Step 3: If the n is smaller than m, then you would find n in
the first half ,if the array is arranged in ascending order.Then
you dont want the second part anymore.discard it. So the
length changes after you discard the second part.Lower index
value remains the same that is 0, but upper limit becomes
middle value - 1.Then step 2 will be repeated.
If the n is bigger than m, then you would find n in the second
half ,if the array is arranged in ascending order.Then you
dont want the first part anymore.discard it. So the length
changes after you discard the second part.Upper index value
remains the same, but lower limit becomes middle value +
1.Then step 2 will be repeated.
Example :
The array is
14 , 23, 28, 36, 69, 88
The number to be searched is 23.
Step 1:
Middle value = (lower index +Upper index)/2
= (0+5)/2
= 2.5
Either round off or truncate it. Let us take 3.So the middle value is 36.
Step 2 :
Compare 23 and 3 rd element 36.Both are not same.
Step 3 :
23 is smaller than 36, that means 23 will not be there after 36.
so discard second half, that is elements after 36.Lower index is still 0, and upper index becomes the value before the middle value , i.e 28.
Checking will go on till it finds the value.
If the value to be searched is 88 then,
88 is bigger than 36, therefore 88 will not be in the list
before 36.
so discard first half, that is elements before 36.upper
index remains the same and lower index becomes the
value after the middle value.
Checking will go on till it finds the value. Otherwise it will print the nmber not in the list.
class binary
{
public static void main(int a[],int n)---------------------------1
{
int l,i,mid,place,flag=0;
l=a.length;--------------------------------------------------------2
int low=0,up= l -1;----------------------------------------------3
while(low <= upp)----------------------------------------------4
{
mid = (low+up)/2;------------------------------------------5
if(a[mid]==n)
{
flag=1;------------------------------------------------6
place=mid;--------------------------------------------7
break;-------------------------------------------------8
}
else if(a[mid] < n)-----------------------------------------9
low=mid+1;
else
upp=mid - 1;
}
if(flag==1)
System.out.print(n+"is found at+(place+1));-----------------10
else
System.out.print(n+"is not found ");
}
}
step 1: input the array, number to be searched
step 2: find the length of the array
step 3:initialize the values for lower and upper index. l-1 coz, index starts from 0.
step 4:the loop should continue as long as lower limit is less than upper limit.
step 5:find the middle value.common mistake here is
(a[low]+a[upp])/2
step 6:there is some variable with some intial value so that when we find the number, change that value.If the value is not changed then it means the number is not found,coz you would not have gone to step 6.
step 7: if you want to find exactly where the number occurs in the array,then assign the mid index, not mid value.It is not a[mid].
step 8:Once we found the number,come out. no more searching.
step 9:check the number with middle value , change the low or upper index accordingly.
Isn't that easy.
No comments:
Post a Comment