**by BehindJava**

# How to implement Binary Search Algorithm in Data Structures using Java

In this blog, we are going to learn about implementing the Binary Search Algorithm in Data Structures using Java.

# Binary Search

- The binary search is the standard algorithm for searching through a sorted sequence.
- It is much more efficient than the sequential search, but it does require that the elements be in order.
- It repeatedly divides the sequence in two, each time restricting the search to the half that would
- Contains the element.
- You might use the binary search to look up a word in a dictionary.

# Algorithm

(Binary search) BINARY(DATA, LB, UB, ITEM, LOC) Here DATA is a sorted array with lower bound LB and upper bound UB, and ITEM is a given item of information. The variables BEG, END and MID denote, resp., the beginning, end, and middle locations of a segment of elements of DATA. The algo finds the location LOC of ITEM in DATA or sets LOC = NULL.

- [Initialize segment variables.] Set BEG := LB, END := UB and MID := INT((BEG + END) / 2).
- Repeat steps 3 and 4 while BEG <= END and DATA[MID] != ITEM.
- If ITEM < DATA[MID], then: Set END := MID – 1. Else: Set BEG := MID + 1.\ [End of If.]
- Set MID := INT((BEG + END)/2). [End of Step 2 loop.]
- If DATA[MID] = ITEM, then: Set LOC := MID. Else: Set LOC := NULL. [End of If.]
- Exit

# Performance

- The binary search runs in O(lg n) time.
- This means that, on average, the running time is proportional to the logarithm of the number of elements in the array.
- So if it takes an average of T milliseconds to run on an array of n elements, then will take an average of 2T milliseconds to run on an array of n2 elements.
- For example, if it takes 3 ms to search 10,000 elements, then it should take about 6 ms to search 100,000,000 elements!
- Each iteration of the loop searches a subarray that is less than half as long as the subarray on the previous iteration.
- Thus the total number of iterations is no more than the number of times that the length n can be divided by 2. That number is lg n.
- And the total running time is roughly proportional to the number of iterations that the loop makes.

# Binary Search in Java

```
public class BehindJava {
public static void main(String[] args) {
int[] intArray = { -22, -15, 1, 7, 20, 35, 55 };
System.out.println("Found at Location:"+iterativeBinarySearch(intArray, -15));
System.out.println("Found at Location:"+iterativeBinarySearch(intArray, 35));
System.out.println("Found at Location:"+iterativeBinarySearch(intArray, 8888));
System.out.println("Found at Location:"+iterativeBinarySearch(intArray, 1));
System.out.println("Found at Location:"+recursiveBinarySearch(intArray, -15));
System.out.println("Found at Location:"+recursiveBinarySearch(intArray, 35));
System.out.println("Found at Location:"+recursiveBinarySearch(intArray, 8888));
System.out.println("Found at Location:"+recursiveBinarySearch(intArray, 1));
}
public static int iterativeBinarySearch(int[] input, int value) {
int start = 0;
int end = input.length;
while (start < end) {
int midpoint = (start + end) / 2;
System.out.println("midpoint = " + midpoint);
if (input[midpoint] == value) {
return midpoint;
} else if (input[midpoint] < value) {
start = midpoint + 1;
} else {
end = midpoint;
}
}
return -1;
}
public static int recursiveBinarySearch(int[] input, int value) {
return recursiveBinarySearch(input, 0, input.length, value);
}
public static int recursiveBinarySearch(int[] input, int start, int end, int value) {
if (start >= end) {
return -1;
}
int midpoint = (start + end) / 2;
System.out.println("midpoint = " + midpoint);
if (input[midpoint] == value) {
return midpoint;
} else if (input[midpoint] < value) {
return recursiveBinarySearch(input, midpoint + 1, end, value);
} else {
return recursiveBinarySearch(input, start, midpoint, value);
}
}
}
```

Output:

```
midpoint = 3
midpoint = 1
Found at Location:1
midpoint = 3
midpoint = 5
Found at Location:5
midpoint = 3
midpoint = 5
midpoint = 6
Found at Location:-1
midpoint = 3
midpoint = 1
midpoint = 2
Found at Location:2
midpoint = 3
midpoint = 1
Found at Location:1
midpoint = 3
midpoint = 5
Found at Location:5
midpoint = 3
midpoint = 5
midpoint = 6
Found at Location:-1
midpoint = 3
midpoint = 1
midpoint = 2
Found at Location:2
```

# Comparison between Binary Search and Linear Search

Binary search operates on sorted lists | Linear search can operate on unsorted Lists as well. |
---|---|

Binary search is complex as compared to linear search. | Linear search is simple and straight forward to implement than the Binary Search. |

Binary Search is considered to be a more efficient method that could be used with large lists. | But, Linear search is too slow to be used with large lists due to its O(n) average case performance. |

Number of comparisons are less | More number of comparisons are required if the items are present in the later part of the array or its elements are more. |

Works well with arrays and not on linked lists. | Works with arrays and linked lists. |