The Binary Search in Java

Filed Under: Java
Binary Search In Java

Introduction

In this tutorial, we are going to learn about the Binary Search algorithm and implement it in Java.

Normal Linear or sequential search algorithm is convenient to use for a small set of data. When the size increases, then in the worst case we require 2n comparisons, where the size of an array or list is n.

Thus we require more efficient algorithms for searching elements. In this tutorial, we are going to explore how binary search is a simple and efficient algorithm as well as how it works.

The Core Algorithm of Binary Search

For Binary Search, the elements in an array must be in sorted order. Let us consider an array that is in ascending order. The Binary search compares elements to be searched, that is, the key with the element present in the middle of the data set. It is based on the following three(3) basic conditions:

  1. if the key is less than the middle element, then we now need to search only in the first half of the array,
  2. If the key is greater than the middle element, then we need to only search in the second half of the array,
  3. And if the key is equal to the middle element in the array, then the search ends,
  4. Finally, if the key is not found in the whole array, then it should return a none or -1. This indicates the element to be searched is not present.

Example of Binary Search

Consider a sorted array of 10 integers as given below,

Given Array
Given Array

Suppose we are searching for the element 48. In this case, our key is 48.

Bs1
Figure 1

Now, we will have to compare the middle element, which is 25 with the element that we need to search(48). Since 48>25, we eliminate the first half and will have to search in the second half for the key.

Further for doing that, we set low as Mid + 1 and high as the size of the array – 1 or, index of the last element.

Bs2
Figure 2

In the next iteration, we compare the middle element 55 with the key. Since 48<55, we will have to search the element again in the left half of the array. Correspondingly, the values of low and high are updated as 5(no change) and Mid – 1.

Bs3
Figure 3

Nextly, now the middle element is 28 for which we have 48>28. Hence, we need to further consider the right portion of the array.

For which now, low = Mid + 1=6, and high = 6 (no change).

Bs4
Figure 4

For the next iteration, the middle element is equal to the element to be searched, i.e., 48.

So, we found the number at index 6(Mid).

Implementing Binary Search in Java

Now let us implement the above-mentioned Binary Search Algorithm in java.

public class BinarySearch
{  
    public static int binarySearch(int arr[], int low, int high, int key)
    {  
        int mid = (low + high)/2;  
        while( low <= high )
        {  
            if ( arr[mid] < key )
            {  
                low = mid + 1;     
            }
            else if ( arr[mid] == key )
            {
                return mid;  
            }else
            {  
                high = mid - 1;  
            }  
            mid = (low + high)/2;  
        }  
        if ( low > high )
        {   
            return -1;
        }  
        return -1;
   }  
   public static void main(String args[])
   {  
        int arr[] = {10,18,19,20,25,28,48,55,62,70};  
        int key = 48;  
        int n=arr.length-1;  
        int index = binarySearch(arr,0,n,key);  
        System.out.println("The sorted array is: ");
        for(int i=0;i<n;i++)
        {
            System.out.print(arr[i] + " ");
        }
        System.out.println("\nElement to be searched: "+key);
        if (index == -1)  
            System.out.println("Unfortunately the Element is not found!");  
        else  
            System.out.println("The Element is found at the index: "+index);  
   }  
}  

Output:

Binary Search In Java
Binary Search In Java

Complexities of the Binary Search Algorithm

The average number of comparisons for the binary search algorithm is log2N. Hence, the time complexity of Binary Search is log2n.

In terms of space complexity, for binary search, it is O(log n). In addition, it takes O(n) space to store the array.

Where n is the size of the given sorted array.

Conclusion

So, in this tutorial, we learned about the Binary Search Algorithm and its implementation in Java. For clear understanding try out the code yourself. For any further questions feel free to use the comments below.

References

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages