Binary Search in Java
In binary search the array must be in sorted order either ascending
or descending order. Binary search relies on divide and conquer strategy in a
sorted list. In Binary
Search we split the array into two half. And then check the search value, if
the value is less than the mid value then we will only look First half otherwise
Second half. In this way we will search until the value found.
Logic :
In this example I have declare array
num[]. After then I insert the value. Then with the help of Bubble sort
algorithm we do the sorting. After then a search value has taken. Here first of
all the desired elements compared with the middle most elements of the array.
If the search element is smaller to
the middle most elements then process is repeated with the first half of the
array.
If the search element is greater to
the middle most elements then process is repeated with the second half of the
array.
If the search element is equal to the
middle most elements search is completed and position is return in ‘pos ‘
variable.
import java.io.*;
/**
* BinarySearchInJava
* Array
must be in sorted order for Binary search
*/
public class BinarySearchInJava
{
public static void main(String args[]) throws IOException
{
int num[] = new int[10];
int i,s,f=0,t,j;
int low, high, mid, pos;
InputStreamReader in=new
InputStreamReader(System.in);
BufferedReader br=new
BufferedReader(in);
System.out.println("Enter elements
in array:");
for(i=0;i<10;i++)
{
num[i] = Integer.parseInt(br.readLine());
}
System.out.println("Enter element
to Search:");
s = Integer.parseInt(br.readLine());
// Sorting of array
for(i=0;i<9;i++)
{
for(j=0;j<9-i;j++)
{
if(num[j] > num[j+1])
{
t = num[j];
num[j] = num[j+1];
num[j+1] = t;
}
}
}
System.out.println("Sorted
array:");
for(i=0;i<10;i++)
{
System.out.print(num[i] + "
");
}
// Binary Search
high=10;
low=0;
pos=0;
while(low <= high)
{
mid = (low + high) / 2;
if(s < num[mid])
{
high = mid - 1;
}
else if(s>num[mid])
{
low = mid + 1;
}
else if(s == num[mid])
{
pos = mid + 1;
break;
}
}
System.out.println("\n Search
result");
System.out.println(s+" is located
at " + pos);
}
}
Output:
Enter
elements in array:
10
7
8
4
5
6
9
1
2
3
Enter element
to Search:
4
Sorted array:
1 2 3 4 5 6 7 8 9 10
Search result
4 is located
at 4
Variable
Description for Java:
Sl. No.
|
Variable Name
|
Data Type
|
Purpose
|
1
|
main()
|
void
|
Main function
|
2
|
num[]
|
int
|
To store the values in an array
|
3
|
i , j
|
int
|
For running the loop
|
4
|
s
|
int
|
To store the input (element to be
searched)
|
5
|
t
|
int
|
For temporarily storing a value
|
6
|
low
|
int
|
value in the lowest
position
|
7
|
mid
|
int
|
value in the middle
position
|
8
|
high
|
int
|
value in the highest
position
|
9
|
pos
|
int
|
position of the value
which was searched(only if exists)
|
10
|
in
|
InputStreamReader
|
To instantiate the InputStreamReader
class which exists in java.iopackage
|
11
|
br
|
BufferedReader
|
To instantiate the BufferedReader
class which exists in java.iopackage using the above variable as
passing parameter
|
Analysis:
Here we are
reducing the search area. Here number of comparisons keeps on decreasing. In
worst case scenario log(N + 1), that is why it is an efficient search compared
to Linear Search.
