Binary Search in Java

May 19, 2025

Binary Search in Java Programming Language

Before moving on to Binary search in Java language….let you know that it is a fundamental algorithm in computer science used to efficiently find an element in a sorted array.

Unlike linear search, which checks each element one by one, binary search divides the array into halves and eliminates one half during each iteration, significantly reducing the number of comparisons.

This article will cover the concept, implementation, time complexity, variations, and practical applications of Binary Search in Java.

How Binary Search Works ?

  1. Binary search operates by repeatedly dividing the search interval in half.
  2. If the target value is less than the middle element, the algorithm continues the search on the left half.
  3. If the target value is greater, it searches the right half.
  4. This process continues until the target value is found or the search interval is empty.

Binary Search Algorithm: Step by Step

  1. Initialization: Set low = 0 and high = array.length - 1.

  2. Calculation of Midpoint: mid = low + (high - low) / 2

  3. Comparison:

    • If array[mid] == target, return mid.

    • If array[mid] < target, update low = mid + 1.

    • If array[mid] > target, update high = mid - 1.

  4. Termination: The algorithm terminates when low > high or when the target value is found.

Space and Time Complexity

Time Complexity (Best)Ω(1)
Time Complexity (Avg)Θ(log n)
Time Complexity (Worst)O(log n)
Space ComplexityO(1)

 

Edge Cases and Considerations

  • Handling overflow when calculating the midpoint using low + (high – low) / 2.
  • Ensuring that the array is sorted before applying binary search.
  • Dealing with duplicate elements in the array.

Linear Search In Java

Linked List in Java

Singly Linked List in Java

Doubly Linked List in Java

Circular Linked List in Java

Arrays with Java

Learn DSA

Learn DSA with Java
Binary Search in Java

Working of Binary Search in Java….

  1. For Binary Search to be performed on any array, the array must be already sorted in any format, that is, either ascending or descending.
  2. Find the middle index of the array/list.
  3. If the middle element is equal to the search element, Stop Searching.
  4. If the element that is to be searched is less then the middle element then consider the first half as a separate list.
  5. Else-If the element that is to be searched is larger then the middle element then consider the second half as a separate list.
  6. Repeat Step 2-3-4-5 Until desired result is found.

Algorithm of Binary Search in Java….

  • while(left<=right)
          mid=left + (right – left)/2;
  • if(a[mid]<search_element)
          left=mid+1;
  • else if(a[mid]>search_element)
          right=mid-1;
  • If found return index+1
  • Else return -1

Explaining the Binary Search Concept in Java

Binary-Search-in-Java-Example

Methods Discussed

We will be discussing two methods for the same

  • Recursive Approach
  • Iterative Approach

1. Binary Search in Java (Recursive Approach)

  • Iterative approach uses a loop to repeatedly divide the search space in half.

  • It maintains low and high pointers and adjusts them based on the comparison with the middle element.

  • This approach is space efficient as it does not require additional stack space.

Advantages:

  1. More space efficient compared to recursion.
  2. Easier to debug and trace since it avoids stack overflow issues.

Disadvantages:

The logic can be slightly more complex compared to recursion due to explicit handling of the loop.

Run 
// Binary Search implimentation in Java (Recursive)
// Time Complexity : O(N)
// Space Complexity : O(1)
// Auxiliary Space Complexity : O(N) due to function call stack
public class Main{

    public static int binarySearch(int array[], int left, int right, int item){

        if (right >= left){

            // calculation of new mid
            int mid = left + (right - left)/2;

            // returns position where found
            if (array[mid] == item)
                return mid+1;

            // goes to recursive calls in left half
            if (array[mid] > item)
                return binarySearch(array, left, mid-1, item);

                // goes to recursive calls in right half
            else
                return binarySearch(array, mid+1, right, item);
        }
        // if element is not found we return -1
        else
            return -1;
    }
    public static void main(String args[]){

        int[ ] array = {10, 20, 30, 40, 50, 60, 70, 80};
        int item = 70;
        int size = array.length;

        int position = binarySearch(array, 0, size-1, item);

        if(position == -1)
            System.out.println("Element not found");
        else
            System.out.println("The value " + item + " found at position: " + position);

    }
}
// Time complexity O(Log N)

Output

The value 70 found at position: 7

Binary Search in Java (Iterative Approach)

Let us look at the iterative approach below:

  • The recursive approach calls the same function with adjusted low and high pointers based on the comparison.

  • It uses the call stack to keep track of the current state, resulting in a space complexity of O(log n).

Advantages:

  • Simplified logic due to inherent stack structure.
  • Easier to implement and understand in terms of algorithmic flow.

Disadvantages:

  • Additional space overhead due to recursive stack frames.
  • Risk of stack overflow for large arrays.
Run 
// Binary Search implementation in Java (Recursive)
// Time Complexity : O(N)
// Space Complexity : O(1)
// Auxiliary Space Complexity : O(N) due to function call stack
public class Main{

    public static int binarySearch(int arr[], int left, int right, int item){

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // if item is at mid
            if (arr[mid] == item)
                return mid;

            // If item greater, ignore left half, consider only right half
            if (arr[mid] < item)
                left = mid + 1;

                // If item is smaller, ignore right half, consider only left half
            else
                right = mid - 1;
        }

        // if we are able to reach here
        // means item wasn't present
        return -1;
    }
    public static void main(String args[]){

        int[ ] array = {10, 20, 30, 40, 50, 60, 70, 80};
        int item = 70;
        int size = array.length;

        int position = binarySearch(array, 0, size-1, item);

        if(position == -1)
            System.out.println("Element not found");
        else
            System.out.println("The value " + item + " found at position: " + position);

    }
}

Output

The value 70 found at position: 6

Conclusion:

  1. Binary search is an efficient algorithm for finding elements in a sorted array with a time complexity of O(log n).
  2. The iterative approach uses constant space, while the recursive approach uses additional space due to the call stack.
  3. Choosing between them depends on space constraints and implementation preference.

Learn DSA

Learn DSA with Java

FAQ's Related Binary Search in Java

Answer:

The time complexity of binary search in Java is O(log n) in both recursive and iterative methods.

 

Answer:

Because each recursive call adds a new frame to the call stack, resulting in a space complexity of O(log n).

Answer:

Iterative binary search repeatedly divides the search range in half using a loop until the target is found or the range is empty.

Answer:

Iterative binary search is generally preferred due to its constant space complexity O(1) compared to O(log n) for the recursive method.

 

Answer:

No, binary search requires the array to be sorted in ascending order for it to work correctly.