Table of contents
1.
Introduction
2.
Binary Search Algorithm Java
3.
Methods for Java Binary Search
3.1.
1. Recursive Method for Binary Search Java
3.2.
2. Iterative Method for Binary Search Java
3.3.
3. Implementation of Built-in Binary Search in Java
3.4.
Time Complexity
4.
Binary Search in Java Collections
5.
Frequently Asked Questions
5.1.
What is a binary search in Java?
5.2.
What is the formula for binary search in Java?
5.3.
What is the main advantage of binary search in Java?
5.4.
How to perform Binary search in Java?
6.
Conclusion
Last Updated: Dec 3, 2024
Medium

Binary Search in Java

Author Manvi Chaddha
2 upvotes
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Binary search is the most widely used searching algorithm used to search an item from a sorted list; It is also known as half interval search, logarithmic search, and binary chop. Using binary search takes the time complexity of O(log N) as compared to linear searching an item that takes the time complexity of O(N), where N is the number of items in the search space. 

Binary Search in Java

This blog will discuss Binary Search program in Java in complete detail.

Binary Search Algorithm Java

  • Take two pointers, left equal to 0 and right equal to the size of the list for the leftmost and the rightmost element of the list of items.
  • Find the middle index, using the formula
  • middle = left + (right-left)/2.
  • Compare the target element with the element at the middle position.
  • If the target element equals the middle element, the element is found. You can return the index of the element.
  • If the target element is greater than the middle element, you need to search in the subarray from the middle element to the rightmost element.
  • Else you need to search in the range from the leftmost element to the middle element.

Methods for Java Binary Search

  1. Recursive Method
  2. Iterative Method
  3. Inbuild Method

1. Recursive Method for Binary Search Java

Implementation of Recursive Binary Search Java:

// Recursive binary search Java Implementation
public class BinarySearchJavaRecursive
{
 static int binarySearch(int arr[], int left, int right, int x)
    {
        if (right >= left) {
            int mid = left + (right - left) / 2;
 
            // If the element is present at the
            // middle itself
            if (arr[mid] == x)
                return mid;
 
            // If element is smaller than mid, then
            // it can only be present in left subarray
            if (arr[mid] > x)
                return binarySearch(arr, left, mid - 1, x);
 
            // Else the element can only be present
            // in right subarray
            return binarySearch(arr, mid + 1, right, x);
        }
 
        // We reach here when element is not present
        // in array
        return -1;
    }
   
    public static void main(String[] args)
    {
        int[] array = {10, 13, 34, 45, 56, 60, 70};
        int key = 56;
        int index = binarySearch(array, 0, array.length-1, key);
        if(index == -1){
            System.out.println("Element not found");
        }
        else{
        System.out.println("The index of " + key + " is " + index);
        }
    }


}
You can also try this code with Online Java Compiler
Run Code

 

Output:

The index of 56 is 4

2. Iterative Method for Binary Search Java

// Iterative Binary Search Java Implementation
public class BinarySearchJavaIterative {
    // Returns index of x if it is present in arr[],
    // else return -1
    static int binarySearch(int arr[], int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int middle = left + (right - left) / 2;


            // Check if x is present at mid
            if (arr[middle] == target)
                return middle;


            // If x greater, ignore left half
            if (arr[middle] < target)
                left = middle + 1;


            // If x is smaller, ignore right half
            else
                right = middle - 1;
        }


        // if we reach here, then element was
        // not present
        return -1;
    }


    public static void main(String[] args) {
        int[] arr = { 10, 13, 24, 35, 46, 57, 68 };
        int target = 68;
        int res = binarySearch(arr, target);
        if (res == -1) {
            System.out.println("Element not found");
        } else {
            System.out.println("Element found at index " + res);
        }
    }
}
You can also try this code with Online Java Compiler
Run Code

 

Output:

Element found at index 6

3. Implementation of Built-in Binary Search in Java

Java provides an in-built method for binary search in the java.util.Arrays class. The method Arrays.binarySearch() efficiently searches for a specific element in a sorted array and returns its index if found. If the element is not present, it returns a negative value indicating the insertion point.

Here’s the implementation:

import java.util.Arrays;

public class BinarySearchExample {
    public static void main(String[] args) {
        // Sorted array
        int[] arr = {10, 20, 30, 40, 50, 60, 70};
        
        // Element to search
        int key = 40;
        
        // Using Arrays.binarySearch()
        int result = Arrays.binarySearch(arr, key);
        
        // Output the result
        if (result >= 0) {
            System.out.println("Element " + key + " found at index: " + result);
        } else {
            System.out.println("Element " + key + " not found. Insertion point: " + (-result - 1));
        }
    }
}
You can also try this code with Online Java Compiler
Run Code

Output

If the element exists in the array:

Element 40 found at index: 3

If the element does not exist in the array (e.g., key = 35):

Element 35 not found. Insertion point: 3

Time Complexity

The time complexity of the binary search is O(logN), where N is the size of the array. 

Binary Search in Java Collections

Java Collections framework provides the Collections.binarySearch() method to perform binary search on a List. The list must be sorted in natural order or by a comparator for accurate results. The method returns the index of the element if found or a negative value indicating the insertion point.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BinarySearchInCollections {
    public static void main(String[] args) {
        // Sorted list
        List<Integer> list = new ArrayList<>();
        Collections.addAll(list, 10, 20, 30, 40, 50, 60, 70);
        
        // Element to search
        int key = 40;
        
        // Using Collections.binarySearch()
        int result = Collections.binarySearch(list, key);
        
        // Output the result
        if (result >= 0) {
            System.out.println("Element " + key + " found at index: " + result);
        } else {
            System.out.println("Element " + key + " not found. Insertion point: " + (-result - 1));
        }
    }
}
You can also try this code with Online Java Compiler
Run Code

Output

If the element exists:

Element 40 found at index: 3

If the element does not exist (e.g., key = 35):

Element 35 not found. Insertion point: 3

Frequently Asked Questions

What is a binary search in Java?

Binary search is an efficient algorithm in Java for finding the position of a target element in a sorted array or list. It works by repeatedly dividing the search interval in half until the target is found or the interval is empty.

What is the formula for binary search in Java?

The formula to find the middle index in binary search is:
mid = low + (high - low) / 2
This prevents integer overflow compared to using (low + high) / 2. Adjust low or high based on comparisons.

What is the main advantage of binary search in Java?

The main advantage of binary search is its efficiency, with a time complexity of O(log n). It significantly reduces the number of comparisons required compared to linear search, making it ideal for large, sorted datasets.

How to perform Binary search in Java?

Binary searching works by comparing an input value to the middle element of the array. The comparison determines whether the element equals the  input, is less than the input, or greater than the input. 

Conclusion

Binary search is a highly efficient algorithm for finding elements in sorted arrays or lists in Java. With a time complexity of O(log n), it outperforms linear search, especially for large datasets. By understanding the underlying mechanics and using built-in methods like Arrays.binarySearch() and Collections.binarySearch(), developers can optimize search operations in their Java projects.

Recommended problems:

Recommended Articles:`

  • Iteration Statements in Java
  • Duck Number in Java
  • Hashcode Method in Java 
  • Swap Function in Java
Live masterclass