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.

how binary search works in java

binary search in java

As you can see above image we have a sorted array of size 5.

Now given an array, we have to find whether key element exist in the given array or not.

Also read – linear search in java

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 equal to 20 and we want to find whether 20 exists in the array.

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

Also read – sort string array java

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. Now we compare it with the middle element which is 30.

Key element is less than 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.

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 in java using recursion

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 in java using scanner

Here’s the java program on binary search using scanner.

import java.util.Scanner;
public class UsingScanner 
{
   public static void main(String[] args) 
   {
      int first, last, middle;
      Scanner sc = new Scanner(System.in);
      System.out.println("Please enter number of elements to search: ");
      int num = sc.nextInt();
      int[] arrNumbers = new int[num];
      System.out.println("Please enter " + num + " elements: ");
      for(int a = 0; a < num; a++)
         arrNumbers[a] = sc.nextInt();
      System.out.println("Please enter search value: ");
      int search = sc.nextInt();
      first = 0;
      last = num - 1;
      middle = (first + last) / 2;
      while(first <= last)
      {
         if(arrNumbers[middle] < search)
            first = middle + 1;
         else if(arrNumbers[middle] == search)
         {
            System.out.println(search + " found at location " + (middle + 1) + ".");
            break;
         }
         else
         {
            last = middle - 1;
         }
         middle = (first + last) / 2;
      }
      if(first > last)
         System.out.println(search + " is not found.");
      sc.close();
   }
}


Output:

Please enter number of elements to search: 5
Please enter 5 elements:
55
17
29
27
42
Please enter search value: 29
29 found at location 3.

Please enter number of elements to search: 5
Please enter 5 elements:
89
96
67
43
28
Please enter search value: 24
24 is not found.


Never stop learning. Grow your knowledge in java programming and coding.