Binary search in java

Let’s learn what is a binary search in java?

Binary search in java

Binary search is the process of searching key element from sorted array.

Binary search algorithm java

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

binary search in java

Now given an array, we have to find whether key element exist 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.

binary search in java

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

public class BinarySearchExample
{
   public static void binarySearch(int[] arrNumbers, int start, int end, int keyElement)
   {
      int middle = (start + end) / 2;
      while(start <= end)
      {
         if(arrNumbers[middle] < keyElement)
         {
            start = middle + 1;
         }
         else if(arrNumbers[middle] == keyElement)
         {
            System.out.println("Element found at index: " + middle);
            break;
         }
         else
         {
            end = middle - 1;
         }
         middle = (start + end) / 2;
      }
      if(start > end)
      {
         System.out.println("Element not found!");
      }
   }
   public static void main(String[] args)
   {
      int[] arrNumbers = {14,15,16,17,18};
      int keyElement = 16;
      int end = arrNumbers.length - 1;
      binarySearch(arrNumbers, 0, end, keyElement);
   }
}

Output:

Element found at index: 2


Binary search using recursion in java

Here’s binary search using recursion (recursive).

public class BinarySearchRecursion
{
   int binaryRecursion(int[] arrNum, int left, int right, int m)
   {
      if(right >= left)
      {
         int mid = left + (right - left) / 2;
         // checking if element is present in middle
         if(arrNum[mid] == m)
            return mid;
         // checking if element is small than middle element
         if(arrNum[mid] > m)
            return binaryRecursion(arrNum, left, mid - 1, m);
         // if not element can only be present in right
         return binaryRecursion(arrNum, mid + 1, right, m);
      }
      // we come out of the loop if not present in array
      return -1;
   }
   public static void main(String[] args)
   {
      BinarySearchRecursion bsr = new BinarySearchRecursion();
      int[] arrBinary = {1,4,6,14,32};
      int num = arrBinary.length;
      int a = 14;
      int result = bsr.binaryRecursion(arrBinary, 0, num - 1, a);
      if(result == -1)
      {
         System.out.println("Sorry!!Element is not present");
      }
      else
      {
         System.out.println("Element found at index " + result);
      }
   }
}

Output:

Element found at index 3


Binary search using iterative approach

Here’s the code.

public class BinaryIterativeDemo
{
   // here code returns index of variable y in the array else return -1
   int searchBinary(int[] arrNum, int y)
   {
      int left = 0, right = arrNum.length - 1;
      while(left <= right)
      {
         int m = left + (right - left) / 2;
         // checking if variable y is present at middle
         if(arrNum[m] == y)
            return m;
         // check if variable y is greater, neglect left
         if(arrNum[m] < y)
            left = m + 1;
         // check if variable y is smaller, neglect right
         else
            right = m - 1;
      }
      // we come out of the loop if not present in array
      return -1;
   }
   public static void main(String[] args)
   {
      BinaryIterativeDemo bs = new BinaryIterativeDemo();
      int[] arrBinary = {1, 4, 6, 14, 32};
      int x = 32;
      int output = bs.searchBinary(arrBinary, x);
      if(output == -1)
      {
         System.out.println("Sorry!!Element not present");
      }
      else
      {
         System.out.println("Element found at index " + output);
      }
   }
}

Output:

Element found at index 4


Binary search time complexity:

T(n) = T(n/2) + c


Binary search example in java using Arrays.binarySearch()

We can also execute above example using Arrays.binarySearch() method.

import java.util.Arrays;
public class UsingArraysBinarySearch
{
   public static void main(String[] args)
   {
      int[] arrNumbers = {15,16,17,18,19};
      int keyElement = 17;
      int output = Arrays.binarySearch(arrNumbers, keyElement);
      if(output < 0)
      {
         System.out.println("Element not found!");
      }
      else
      {
         System.out.println("Element found at index: " + output);
      }
   }
}

Output:

Element found at index: 2


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