Binary search in java

Let’s learn binary search in java.

Binary search in java

Binary search is the process of searching key element from sorted array by frequently dividing in search space in half.

Binary search algorithm java

As you can see in the below image we have a sorted array of size 5.

Now given an array, we have to find whether key element exists in the given array or not. If key element exist in the above array, then find the index position where it exists.

Before that we have to declare three variables start, middle element and end.

Here to find middle element

middleelement = (start + end) / 2;

Let’s say key element to search is 20 and we want to find whether 20 exists in the array or not. Now we compare it with the middle element which is 30.

Key element is less than middle element 30. So it should exist somewhere before 30. We discard all the elements after 30 and 30 as well. We need to search key element only between index 0 and 1.

Now if key element is equal to the middle element, our search is over. Because we have found key element in the array.

If key element is less than the middle element, then it lies before the middle element and we can discard middle element and all the elements after middle element.

And if key element is greater than the middle then it lies after the middle element so we can discard all the elements before the middle element. Initially our search space was whole array.

This kind of search where we reduce the search space into half at each comparison is called binary search.

We are able to reduce the search space into half only because the array is sorted. Here array must be sorted to perform binary search. Here’s binary search program in java.

Binary Example

```class BinarySearchExample
{
public static void main(String[] args)
{
int[] arrNumbers = {2, 4, 6, 8, 10, 12, 14, 16};
int search = 10;
int start = 0;
int end = arrNumbers.length - 1;
int middle = (start + end) / 2;
while (start <= end)
{
if (arrNumbers[middle] == search)
{
System.out.println("Element is at index position " + middle + ".");
break;
}
else if (arrNumbers[middle] < search)
{
start = middle + 1;
}
else
{
end = middle - 1;
}
middle = (start + end) / 2;
}
}
}```

Output:

Element is at index position 4.

Binary Search FAQ’s

Does binary search work on unsorted array?

No. Only sorted array.

What are the steps of binary search in java?

Step 1 – user inputs key search element.
Step 2 – Find middle element in the sorted array.
Step 3 – compare key search element with the middle element in the sorted array.
Step 4 – if both matches, then print element is found!!!” and terminate.
Step 5 – if not, then check whether key search element is smaller or larger than middle element.
Step 6 – if key search element is smaller than middle element, repeat steps 2, 3, 4 and 5 for left sublist of middle element.
Step 7 – if key search element is larger than middle element, repeat steps 2, 3, 4 and 5 for right sublist of middle element.
Step 8 – repeat until key search element is found in array or until sublist contains only one element.
Step 9 – if that element does not match with key search element, then print “Element not found in array!” and terminate.

Is binary search faster than linear search?

Yes. Except for small arrays.

Also read – for each loop in java