For binary search, the array should be arranged in ascending or descending order. Binary search relies on divide and conquer strategy in a sorted list.
Program logic: Take elements in an array called n[]. Then apply bubble sorting algorithm on it. After that a search value has taken. The desired elements is 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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
import java.io.*;
public class BinarySearch {
public static void main(String args[]) throws
IOException {
int n[] = 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++) {
n[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
(n[j] > n[j + 1]) {
t
= n[j];
n[j]
= n[j + 1];
n[j
+ 1] = t;
}
}
}
System.out.println("Sorted
array:");
for (i = 0; i <
10; i++) {
System.out.print(n[i]
+ " ");
}
// Binary Search
high = 10;
low = 0;
pos = 0;
while (low <=
high) {
mid
= (low + high) / 2;
if
(s < n[mid]) {
high
= mid - 1;
}
else if (s > n[mid]) {
low
= mid + 1;
}
else if (s == n[mid]) {
pos
= mid + 1;
break;
}
}
System.out.println("\n
Search result");
System.out.println(s
+ " is located at position " + pos);
}
}
|
Sample Output
Enter elements in array:
5
7
8
4
5
6
9
1
2
3
5
7
8
4
5
6
9
1
2
3
Enter element to Search:
4
4
Sorted array:
1 2 3 4 5 5 6 7 8 9
1 2 3 4 5 5 6 7 8 9
Search result
4 is located at position 4
4 is located at position 4
SN
|
Variables
|
Type
|
Description
|
1.
|
main()
|
Function
|
This is the main entry point of the program
|
2.
|
n[]
|
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
|
To store the value in the lowest position
|
7.
|
mid
|
int
|
To store the value in the middle position
|
8.
|
high
|
int
|
To store the value in the highest position
|
9.
|
pos
|
int
|
To store the 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 of binary
search:
In this algorithm every time we are reducing the search area. So number of comparisons keep on decreasing. In worst case the number of comparison is most log ( N + 1 ). So it is an efficient algorithm when compared to linear search.
In this algorithm every time we are reducing the search area. So number of comparisons keep on decreasing. In worst case the number of comparison is most log ( N + 1 ). So it is an efficient algorithm when compared to linear search.
No comments:
Post a Comment