Table of contents

Introduction

Binary Search Java - Understanding The Problem Statement

2.1.

Binary Search Algorithm Java

2.2.

Example for Binary Search Program in Java

Binary Search Java Implementation

3.1.

Recursive Binary Search Java Implementation

3.2.

Iterative Binary Search Java Implementation

3.3.

Time Complexity

Frequently Asked Questions

4.1.

Where is Binary Search Used?

4.2.

Can we do binary search on unsorted arrays?

4.3.

How to perform Binary search in Java?

Conclusion

Last Updated: Oct 10, 2024

Medium

Binary Search in Java

Author Manvi Chaddha

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.

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

Also, See - Iteration Statements in Java, Duck Number in Java

Binary Search Java - Understanding The Problem Statement

The problem statement on hand is, "Given a list of items in sorted order, find the occurrence of an element x in this list."
Before moving on to the algorithm and Binary search program in Java, let's understand the essence of binary search in a little more detail. Lets try to decode the possible position of a target element considering that we are currently at any random position in the list of items.
If you are at a particular element and the target element is greater than the current one in a sorted list of items. The target element would be present in the right of the current element.

Similarly, if you are searching for an element and the current element is greater than the target element. The target element will be somewhere on the left of the current element.

The question arises, how to choose a current element by which we can compare?
A simple solution is to take any particular element as the current one and then search operation. However, in the worst-case scenario, taking any random element as the current element will make the time complexity O(N). So we are not properly utilizing the fact that the array is sorted. To make the search process effective,

Binary search searches for a particular element by comparing the middlemost item of the list of items; if the element is found at the middle position, then the index of the item is returned; otherwise, if the target element is greater than the item in the middle, then we search in the sub-array to the right of the middle. If the target element is less than the element at the middle, we search in the sub-array to the left of the middle element.
An important point to note is that binary search only works for sorted lists of items, so you cannot use binary search if the list of items is unsorted. You can obviously sort the list of items first using any sorting algorithm and then apply binary search; however, this will make the time complexity O(NLogN) + O (LogN), O(NLog N) for searching, and O(log N) for binary search, making the time complexity greater than linear search.
Binary Search Java is not straightaway asked in an interview, instead it's a general pattern. Questions related to this pattern are prominently asked. A general rule of thumb is whenever you are given a sorted sequence of items, the interviewer is giving you a hint that somehow you have to use binary search. Let’s now look at algorithm, examples and code for Binary Search Java.

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.

Example for Binary Search Program in Java

Let’s take an array of 5 items to understand this algorithm.
arr[] = {10, 13, 34, 45, 56, 60, 70}
You are required to find 56 in this list. The left pointer will be at index 0, and the right pointer will be at the 6th index. The middle pointer will be at
left + (right-left)/2 = 0 + (6-0)/2 = 0 + 3 = 3rd index. The position of pointers is shown in the diagram below.

Since we are only concerned with the subarray to the right of the middle, we will now apply binary search in this subarray. The left, right, and middle pointer position is shown below.

The element at the middle position is 60, greater than the target element 56. So we will now search in the left half of the middle. The left, right, and middle pointer position is shown below.

The pointers at left, right, and middle positions point to the same index, and also the element is also the same as the target element. Hence the element is found. It's highly recommended to try out this algorithm on your own by taking some random examples and then moving to the implementation.
Since we now know the algorithm and practice with an example, let's jump to implementing Binary Search in Java.

Also see, Hashcode Method in Java and Swap Function in Java

Binary Search Java Implementation

Binary Search Java can be implemented either recursively or iteratively. Let’s look at the recursive implementation of Binary Search.

Recursive Binary Search Java Implementation

// 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

Iterative Binary Search Java Implementation

// 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

Time Complexity

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

Check out this problem - First And Last Occurrences Of X

Must Read Recursive Binary Search.

Frequently Asked Questions

Where is Binary Search Used?

Binary search is used in quick searching an item from a sorted sequence of items. Questions related to the binary search are frequently asked in programming interviews.

Can we do binary search on unsorted arrays?

Binary search cannot be done on unsorted arrays. However, you can sort the array and then perform a binary search on it.

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

In this article, we have extensively discussed binary search and its implementation in Java. But this is not enough to truly master binary search you would need to practice problems on it, you can check out Binary Search questions on Code360.

Recommended problems: