Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Binary Search Java - Understanding The Problem Statement
2.1.
Binary Search Algorithm Java
2.2.
Example for Binary Search Program in Java
3.
Binary Search Java Implementation 
3.1.
Recursive Binary Search Java Implementation
3.2.
Iterative Binary Search Java Implementation
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Binary Search in Java

Author Manvi Chaddha
2 upvotes

Introduction

Searching and sorting form an important part of placement preparation; this is the first topic most people start with. In simple terms, searching means retrieving any element from any data structure or a collection of items. A good example of searching is whenever you find any occurrence of a particular word in Microsoft Word or Google docs.

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.

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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);
        }
    }


}

The output of the above program is 
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);
        }
    }
}

The output of the above program is 
Element found at index 6

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.

FAQs

  1.  What is binary search?
     Binary search is a divide and conquer-based search algorithm that repeatedly divides the search space in half.
  2.  What is the time complexity of binary search in Java?
     The time complexity of the binary search is O(log N), where N is the number of elements in the list. Due to the logarithmic time complexity, its regarded as an efficient search algorithm.
  3.  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. 
  4.  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.
  5.  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. 

Key Takeaways

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 Coding Ninjas Studio.  

 

Recommended problems -


We hope that this blog has helped you enhance your knowledge regarding Binary Search. If you would like to learn more, check out our articles on binary search. Do upvote our blog to help other ninjas grow. Happy Coding!

Live masterclass