Binary Search Algorithm In Java – Implementation & Examples

This Tutorial will Explain Binary Search & Recursive Binary Search in Java along with its Algorithm, Implementation, and Java Binary Seach Code Examples:

A binary search in Java is a technique that is used to search for a targeted value or key in a collection. It is a technique that uses the “divide and conquer” technique to search for a key.

The collection on which Binary search is to be applied to search for a key needs to be sorted in ascending order.

Usually, most of the programming languages support Linear search, Binary search, and Hashing techniques that are used to search for data in the collection. We will learn hashing in our subsequent tutorials.

=> Visit Here To Learn Java From Scratch.

Binary Search In Java

Linear search is a basic technique. In this technique, the array is traversed sequentially and each element is compared to the key until the key is found or the end of the array is reached.

Linear search is used rarely in practical applications. Binary search is the most frequently used technique as it is much faster than a linear search.

Java provides three ways to perform a binary search:

1. Using the iterative approach
2. Using a recursive approach
3. Using Arrays.binarySearch () method.

In this tutorial, we will implement and discuss all these 3 methods.

Algorithm For Binary Search In Java

In the binary search method, the collection is repeatedly divided into half and the key element is searched in the left or right half of the collection depending on whether the key is less than or greater than the mid element of the collection.

A simple Binary Search Algorithm is as follows:

1. Calculate the mid element of the collection.
2. Compare the key items with the mid element.
3. If key = middle element, then we return the mid index position for the key found.
4. Else If key > mid element, then the key lies in the right half of the collection. Thus repeat steps 1 to 3 on the lower (right) half of the collection.
5. Else key < mid element, then the key is in the upper half of the collection. Hence you need to repeat the binary search in the upper half.

As you can see from the above steps, in Binary search, half the elements in the collection are ignored just after the first comparison.

Note that the same sequence of steps holds for iterative as well as recursive binary search.

Let’s illustrate the binary search algorithm using an example.

For example, take the following sorted array of 10 elements.

Let’s calculate the middle location of the array.

Mid = 0+9/2 = 4

#1) Key = 21

First, we will compare the key value with the [mid] element and we find that the element value at mid = 21.

Thus we find that key = [mid]. Hence the key is found at position 4 in the array.

#2) Key = 25

We first compare the key value to mid. As (21 < 25), we will directly search for the key in the upper half of the array.

Now again we will find the mid for the upper half of the array.

Mid = 4+9/2 = 6

The value at location [mid] = 25

Now we compare the key element with the mid element. So (25 == 25), hence we have found the key at location [mid] = 6.

Thus we repeatedly divide the array and by comparing the key element with the mid, we decide in which half to search for the key. Binary search is more efficient in terms of time and correctness and is a lot faster too.

Binary Search Implementation Java

Using the above algorithm, let us implement a Binary search program in Java using the iterative approach. In this program, we take an example array and perform binary search on this array.

import java.util.*;
class Main{  
 public static void main(String args[]){  
    int numArray[] = {5,10,15,20,25,30,35}; 
    System.out.println("The input array: " + Arrays.toString(numArray));
    //key to be searched
    int key = 20;
    System.out.println("\nKey to be searched=" + key);
    //set first to first index
    int first = 0;
    //set last to last elements in array
    int last=numArray.length-1; 
    //calculate mid of the array
    int mid = (first + last)/2;  
    //while first and last do not overlap
    while( first <= last ){  
        //if the mid < key, then key to be searched is in the first half of array
        if ( numArray[mid] < key ){  
            first = mid + 1;     
        }else if ( numArray[mid] == key ){ 
            //if key = element at mid, then print the location
            System.out.println("Element is found at index: " + mid);  
            break;  
        }else{  
            //the key is to be searched in the second half of the array
            last = mid - 1;  
        }  
        mid = (first + last)/2;  
   }  
   //if first and last overlap, then key is not present in the array
   if ( first > last ){  
      System.out.println("Element is not found!");  
   }       
 }  
}  

Output:

The input array: [5, 10, 15, 20, 25, 30, 35]
Key to be searched=20
Element is found at index: 3

The above program shows an iterative approach of Binary search. Initially, an array is declared, then a key to be searched is defined.

After calculating the mid of the array, the key is compared to the mid element. Then depending on whether the key is less than or greater than the key, the key is searched in the lower or upper half of the array respectively.

Recursive Binary Search In Java

You can also perform a binary search using the recursion technique. Here, the binary search method is called recursively until the key is found or the entire list is exhausted.

The program that implements a recursive binary search is given below:

import java.util.*;
class Main{  
    //recursive method for binary search
    public static int binary_Search(int intArray[], int low, int high, int key){  
        //if array is in order then perform binary search on the array
        if (high>=low){  
            //calculate mid
            int mid = low + (high - low)/2;  
            //if key =intArray[mid] return mid
            if (intArray[mid] == key){  
            return mid;  
            }  
            //if intArray[mid] > key then key is in left half of array
            if (intArray[mid] > key){  
            return binary_Search(intArray, low, mid-1, key);//recursively search for key  
            }else       //key is in right half of the array
            {  
            return binary_Search(intArray, mid+1, high, key);//recursively search for key 
            }  
        }  
        return -1;  
    }
        public static void main(String args[]){  
        //define array and key
        int intArray[] = {1,11,21,31,41,51,61,71,81,91}; 
        System.out.println("Input List: " + Arrays.toString(intArray));
        int key = 31;  
        System.out.println("\nThe key to be searched:" + key);
        int high=intArray.length-1;
        //call binary search method 
        int result = binary_Search(intArray,0,high,key);  
        //print the result
        if (result == -1)  
            System.out.println("\nKey not found in given list!");  
        else  
            System.out.println("\nKey is found at location: "+result + " in the list");  
    }  
}   

Output:

Input List: [1, 11, 21, 31, 41, 51, 61, 71, 81, 91
The key to be searched:
Key is found at location: 3 in the list

Using Arrays.binarySearch () method.

The Arrays class in Java provides a ‘binarySearch ()’ method that performs the binary search on the given Array. This method takes the array and the key to be searched as arguments and returns the position of the key in the array. If the key is not found, then the method returns -1.

The below example implements the Arrays.binarySearch () method.

import java.util.Arrays;  
class Main{  
    public static void main(String args[]){  
        //define an array
        int intArray[] = {10,20,30,40,50,60,70,80,90};
        System.out.println("The input Array : " + Arrays.toString(intArray));
        //define the key to be searched
        int key = 50;  
        System.out.println("\nThe key to be searched:" + key);
        //call binarySearch method on the given array with key to be searched
        int result = Arrays.binarySearch(intArray,key);  
        //print the return result
        if (result < 0)  
            System.out.println("\nKey is not found in the array!");  
        else  
            System.out.println("\nKey is found at index: "+result + " in the array.");  
    }  
}  

Output:

The input Array : [10, 20, 30, 40, 50, 60, 70, 80, 90]
The key to be searched:50
Key is found at index: 4 in the array.

Frequently Asked Questions

Q #1) How do you write a binary search?

Answer: Binary search is usually performed by dividing the array into halves. If the key to be searched is greater than the mid element, then the upper half of the array is searched by further dividing and searching the sub-array till the key is found.

Similarly, if the key is less than the mid element, then the key is searched in the lower half of the array.

Q #2) Where is the binary search used?

Answer: Binary search is mainly used to search a sorted data in software applications especially when the memory space is compact and limited.

Q #3) What is the big O of binary search?

Answer: The time complexity of the binary search is O (logn) where n is the number of elements in the array. The space complexity of the binary search is O (1).

Q #4) Is binary search recursive?

Answer: Yes. Since binary search is an example of a divide-and-conquer strategy and it can be implemented using recursion. We can divide the array into halves and call the same method to perform the binary search again and again.

Q #5) Why is it called a binary search?

Answer: The binary search algorithm uses a divide-and-conquer strategy that repeatedly cuts the array into halves or two parts. Thus it is named as binary search.

Conclusion

Binary search is the frequently used searching technique in Java. The requirement for a binary search to be performed is that the data should be sorted in ascending order.

A binary search can be implemented either using an iterative or recursive approach. Arrays class in Java also provides the ‘binarySearch’ method that performs a binary search on an Array.

In our subsequent tutorials, we will explore various Sorting Techniques in Java.

=> Watch Out The Simple Java Training Series Here.