Binary search in java

Hey guys!! Welcome to flower brackets blog. Today, we will delve into binary search in java.

binary search in java

Binary search in java

Binary search java 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 in the image above we have a sorted array of integers. Let’s say the name of this array is “numbers”.

int numbers[] = {10, 20, 30, 40, 50};

The size of array is 5. It starts with index 0 to 4. Now given an array or an integer “x”, we have to find out whether “x” exists in this array or not.

If “x” exists in “numbers” array, then we want to find out the 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 the above array? No. 70 does not exist in the array. Now what would be the logic to find out whether “x” exists in “numbers” array or not??

Also read – linear search java

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

If it’s equal to “x”, then we are done with our search, we have found the element in the array. If not, we go to the next element.

And we keep on comparing with the next element until we are finished with the array or we have to find the number. Let’s say, if 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 this binary search algorithm, if we are lucky, 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 – sparse matrix 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

Here there can be three cases

Case one : x == numbers[middleelement]
Case two : x < numbers[middleelement]
Case three : x > numbers[middleelement]

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.

And of course the middle element as well. So in case of 2 and 3 we discard half the elements from our search space and reduce our search space.

In this example when “x” is 20, initially our search space is the whole array. “x” can exist anywhere in the array.

Also read – sort string array java

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

So 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 how do we keep track of the search space? We keep track of the search space using two indices start and end. So initially the start would be 0 and end would be the last element in the array, in this case the index is 4.

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

middleelement = (start + end) / 2;

Once we find 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.

Now we again find the middle element in this reduced space. So here the middle element will be one plus zero by two, if we take only the integral part, one plus zero by two would be zero point 5 (0.5).

If we take the integral part the middle element, it will be index 0. Once again is it equal to “x”? No, 10 is not equal to 20. Is “x” less than the middle element, is it case two? No it is not.

“x” is greater than the middle element, this time we discard the middle element and all the elements towards its left. So “x” is now equal to middle element. We have found our element. So we are done with our search.

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. Ok, let’s see java program for binary search recursive,

Binary search example in java:

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 example in java using iterative approach

Now let’s java program for binary search iterative. 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


Time complexity: 

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

Related Posts