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

Also read – for each loop in java