Binary search in java

Let’s learn binary search in java.

binary search in java

Binary search in java

Binary search algorithm is one of the famous fundamental algorithms in computer science.

We find application in large number of problems. But here let’s try to understand binary search algorithm.

binary search in java

As you can see above image we have a sorted array of integers. The size of array is 5. It starts with index 0 to 4. Now given an array, we have to find whether “x” exists in this array or not.

If “x” exists in “numbers” array, then we want to find position at which “x” exists in this array. For example, if “x” is 40. Does 40 exist in “numbers”array? Yes 40 exists in the array and it exists at index 3.

Does 70 exists in above array? No. 70 does not exist in the array. Now what would be the logic to find whether “x” exists in “numbers” array or not??

Also read – abstraction in java

One simple approach can be that we can scan the whole array to find desired number. So we start at index 0 and compare given element with “x”.

If it is equal to “x”, then we are done with our search. If not, we go to next element.

And we keep on comparing with the next element until we are finished with the array. Let’s say, we wanted to find 30 in the given array. Then our search will be over when we reach index 2.

Suppose we want to find 80 in the above array. Our search will be over at index 4 with the conclusion that 80 does not exist in the array.

This approach will work irrespective of whether the array is sorted or not and if I have to write code for this, it will be pretty straight forward.

Now, with binary search algorithm, we will find “x” at the first position itself. So in the best case we will make only one comparison and we will be able to find the result.

In the worst case when “x” would not even be present in the array, we will scan the whole array and we will make ‘n’ comparisons with all the elements in the array and then we will be able to give back the result that “x” does not exist in the array.

It’s always good to analyze the binary search complexity or running time of an algorithm in the worst case and find the upper bound of the time taken.

Also read – linear search in java

Now in this case the time taken grows as a linear function of “n”. So we also call this as linear search. If we are using linear search, we are not using any property like the array sorted or not, this will work.

Now let us try to improve this binary search algorithm using extra property of the array that it is sorted. Let us say we want to find whether number 20 exists in the array “numbers”.

So “x” is 20 and we want to find whether 20 exists in the array “numbers”. We will use different approach this time, instead of comparing “x” with the first element as we did in the case of linear search, we will compare it with the middle element in the array.

Now the size of this array is 5, so the middle element will be at index 2.

binary search in java

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

If “x” is less than the middle element, then, array is sorted it lies before the middle element and we can discard middle element and all the elements after middle element.

Similarly if “x” is greater than the middle element it lies after the middle element so we can discard all the elements before the middle element.

Initially our search space is the whole array. “x” can exist anywhere in the array. For example let’s say x = 20.

Also read – sort string array java

Now we compare it with the middle element which is 30, “x” is less than 30. So it should exist somewhere before 30.

We discard all the elements after 30 and 30 as well. Now the problem gets redefined. We need to search “x” only between index 0 and 1.

So initially the start would be 0 and end would be the last element in the array, in this case the index is 1.

Because, initially the whole array was our search space and we calculate middle element as

middleelement = (start + end) / 2;

Once we have our reduced search space, we adjust start and end accordingly. In this case, after comparing 20 with 30 and discarding half of the array, our end now becomes index 1.

So here the middle element will be one plus zero divided by two, if we take only the integral part, one plus zero divided by two would be zero point 5 (0.5).

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.

Array being sorted is a precondition for binary search algorithm.

Before going to java program let’s see pseudocode for above explanation. For binary search pseudocode inputs are given array, ‘numbers’ array and element being searched for, that is, x.

  1. Assume minimum elements in given array = 0 and maximum elements = n – 1
  2. Calculate ‘y’ as average of maximum and minimum.
  3. If numbers[y] = x, come to a stop. Element found. Return y.
  4. If y is too low or numbers[y] < x, then minimum = y + 1
  5. Else y is too high. Set maximum = y – 1
  6. Go to step 2

Now, let’s see java program for binary search,

Binary search in java using recursion

Here’s binary search java recursive

public class BinarySearchExample 
{
   int Search(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 Search(arrNum, left, mid - 1, m); 

         // if not element can only be present in right 
         return Search(arrNum, mid + 1, right, m); 
      }
      // we come out of the loop if not present in array 
      return -1; 
   }

   public static void main(String[] args) 
   {
      BinarySearchExample bse = new BinarySearchExample(); 
      int[] arrBinary = {1,4,6,14,32};
      int num = arrBinary.length; 
      int a = 14; 
      int result = bse.Search(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 program in java using for loop

We can also execute binary search using a for loop. Here’s the code,

public class BinarySearchDemo 
{
   public static boolean searchBinary(int[] arr, int value)  
   {
      int start = 0;
      int end = arr.length - 1;              
	     
      for(int a = 0; a < arr.length; a++)   
      {
         int middle = (end - start) / 2;
         if(arr[a] == value)  
         {
            return true;
         }
         else if(arr[middle] > value)  
         {
            end = middle - 1;
         }
         else    
         {
            start = middle + 1;
         }
      }
      return false;
   }

   public static void main(String[] args) 
   {
      int[] arrInput = {1, 4, 6, 14, 32};
      int x = 32; 
      boolean output = searchBinary(arrInput, x); 
      if(output == false)
      {
         System.out.println("Sorry!!Element not present");
      }
      else
      {
         System.out.println("Element found");
      }
   }
}


Output:

Element found

NOTE: binary search program in java using for loop shouldn’t be used because it’s aganist standard coding practice.

By using for loop we will be iterating given array from start to end. This is aganist binary search algorithm.


Binary search for strings in java

Similar to above explanation we can implement binary search on an array of strings.

In binary search for strings first we compare a string, say x, with middle string. If string x matches, then return middle string in the given array.

Else string x is smaller than middle string. Continue search in left half of array if not found search in right half.

Here’s the java string binary search example,

public class BinarySearchString 
{
   // this method returns index of str
   static int binaryString(String[] arrString, String str) 
   { 
      int left = 0, right = arrString.length - 1; 
      while(left <= right) 
      { 
         int middle = left + (right - left) / 2;
         int output = str.compareTo(arrString[middle]);
         // check if str is present at middle 
         if(output == 0) 
            return middle; 

         // If str is greater, ignore left half 
         if(output > 0)
         {
            left = middle + 1;
         }
         // If str is smaller, ignore right half 
         else
         {
            right = middle - 1;
         }
      }
      return -1; 
   }

   public static void main(String[] args) 
   {
      String[] arrInput = { "java", "for", "flower", "brackets" }; 
      String strInput = "for"; 
      int result = binaryString(arrInput, strInput);
      if(result == -1)
      {
         System.out.println("Sorry!!!element not present");
      }
      else
      {
         System.out.println("Element found at " + "index " + result);
      }
   }
}


Output:

Element found at index 1


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.