Binary search is to searching what a scalpel is to surgery—precise, efficient, and surprisingly elegant. Operating in O(log n) time complexity, this algorithm finds elements in sorted arrays up to 20 times faster than linear search for a million-element dataset.

Whether you need binary search in Java for technical interviews, production optimization, or competitive programming, this guide gives you complete code examples you can copy and implement immediately. We'll cover both iterative and recursive approaches, explain the algorithm step-by-step, show you how to leverage Java's built-in Arrays.binarySearch() method, and walk through common interview variations.

By the end, you'll understand why binary search is essential for Java developers working with sorted data and how to apply it in real-world scenarios.

Find high-paying, long-term remote Java jobs with top US, UK, and EU companies at Index.dev. Join now!

What is Binary Search Algorithm?

Binary search is a divide-and-conquer algorithm that finds the position of a target value within a sorted array. Instead of checking each element sequentially (like linear search), binary search repeatedly divides the search interval in half, eliminating half of the remaining elements with each comparison.

Why is Binary Search Algorithm Important?

The binary search algorithm has several uses and therefore it is important for the following reasons. Firstly, it is easily implemented because of the ease of understanding and the simple mathematical algorithm that they use. Second, it also offers high efficiency, especially for big data sets, reducing time complexity to logN. This efficiency is important in areas that necessitate speedy processing of workloads and a fast rate of return. Moreover, the algorithm makes use of logarithmic time complexity thus making it very efficient when working with large data sets because it halves the number of data points on each call.

How Does the Binary Search Algorithm Work?

1. Start with the middle element of the sorted array
2. If the target equals the middle element, return its position
3. If the target is less than the middle element, search the left half
4. If the target is greater than the middle element, search the right half
5. Repeat until the target is found or the search space is empty

Binary search time and space complexity:

Binary search vs. linear search:

For an array of 1,000,000 elements:

• Linear search: Up to 1,000,000 comparisons
• Binary search: Maximum 20 comparisons (log₂ 1,000,000 ≈ 20)

This logarithmic efficiency makes binary search essential for applications handling large datasets, from database indexing to machine learning feature lookup.

Binary Search Program in Java: Complete Code Examples

Here are three ways to implement binary search in Java—iterative, recursive, and using Java's built-in method. Each binary search Java code example is complete and ready to run.

Iterative Binary Search Implementation

The iterative approach uses a while loop and is generally preferred for production code due to its O(1) space complexity:

java
public class BinarySearchIterative {
   
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
       
        while (left <= right) {
            int mid = left + (right - left) / 2; // Prevents integer overflow
           
            if (arr[mid] == target) {
                return mid; // Target found
            } else if (arr[mid] < target) {
                left = mid + 1; // Search right half
            } else {
                right = mid - 1; // Search left half
            }
        }
       
        return -1; // Target not found
    }
   
    public static void main(String[] args) {
        int[] sortedArray = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int target = 23;
       
        int result = binarySearch(sortedArray, target);
       
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in array");
        }
    }
}

Output: Element found at index: 5

Recursive Binary Search Implementation

The recursive approach is more elegant and easier to understand conceptually, though it uses O(log n) stack space:

java
public class BinarySearchRecursive {
   
    public static int binarySearch(int[] arr, int target, int left, int right) {
        if (left > right) {
            return -1; // Base case: target not found
        }
       
        int mid = left + (right - left) / 2;
       
        if (arr[mid] == target) {
            return mid; // Target found
        } else if (arr[mid] < target) {
            return binarySearch(arr, target, mid + 1, right); // Search right
        } else {
            return binarySearch(arr, target, left, mid - 1); // Search left
        }
    }
   
    public static void main(String[] args) {
        int[] sortedArray = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int target = 16;
       
        int result = binarySearch(sortedArray, target, 0, sortedArray.length - 1);
       
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in array");
        }
    }
}

Output: Element found at index: 4

Java Binary Search Using Arrays.binarySearch()

Java's standard library provides a built-in binary search method in the java.util.Arrays class:

java
import java.util.Arrays;

public class JavaBuiltInBinarySearch {
   
    public static void main(String[] args) {
        int[] sortedArray = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
       
        // Search for existing element
        int index = Arrays.binarySearch(sortedArray, 38);
        System.out.println("Index of 38: " + index); // Output: 6
       
        // Search for non-existing element
        int notFound = Arrays.binarySearch(sortedArray, 25);
        System.out.println("Index of 25: " + notFound); // Output: -7 (insertion point)
       
        // The negative value indicates where the element would be inserted
        // Actual insertion point = -(notFound) - 1 = 6
    }
}

Note: When an element is not found, Arrays.binarySearch() returns -(insertion point) - 1, which tells you where the element would be inserted to maintain sorted order.

Read more: Managing Payload and Response Without Java POJOs in Rest-Assured

Common Binary Search Variations and Interview Questions

Binary search in Java appears frequently in technical interviews and competitive programming. Here are essential variations every developer should know:

Finding First/Last Occurrence

When an array contains duplicates, find the first or last occurrence of a target:

java
public static int findFirstOccurrence(int[] arr, int target) {
    int result = -1;
    int left = 0, right = arr.length - 1;
   
    while (left <= right) {
        int mid = left + (right - left) / 2;
       
        if (arr[mid] == target) {
            result = mid;
            right = mid - 1; // Continue searching left for first occurrence
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
   
    return result;
}

Binary Search on Rotated Sorted Array

A classic interview question—search in an array that was sorted then rotated:

java
public static int searchRotated(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
   
    while (left <= right) {
        int mid = left + (right - left) / 2;
       
        if (arr[mid] == target) return mid;
       
        // Determine which half is sorted
        if (arr[left] <= arr[mid]) {
            // Left half is sorted
            if (target >= arr[left] && target < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // Right half is sorted
            if (target > arr[mid] && target <= arr[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
   
    return -1;
}

Finding Square Root Using Binary Search

Binary search works beyond arrays—use it for numerical problems:

java
public static int sqrt(int x) {
    if (x < 2) return x;
   
    long left = 1, right = x / 2;
   
    while (left <= right) {
        long mid = left + (right - left) / 2;
        long square = mid * mid;
       
        if (square == x) return (int) mid;
        else if (square < x) left = mid + 1;
        else right = mid - 1;
    }
   
    return (int) right;
}

Common interview questions using binary search algorithm in Java:

1. Search in a 2D sorted matrix
2. Find peak element in an array
3. Find minimum in rotated sorted array
4. Search insert position
5. Find the median of two sorted arrays

Work from anywhere, get paid well: Apply for remote Java projects on Index.dev. Sign up now →

Performance: Iterative vs. Recursive

While both iterative and recursive implementations share the same O(log n) time complexity, they differ in space efficiency:

• Iterative Binary Search: Uses O(1) space and avoids the overhead of function calls. It's generally safer and slightly faster for production code.
• Recursive Binary Search: Uses O(log n) stack space. While more elegant, it carries a risk of StackOverflowError on extremely large datasets (though rare given the logarithmic depth).

Recommendation: Default to the iterative approach for production Java applications unless the recursive logic significantly improves readability.

Real-World Applications of Binary Search

Binary search powers many systems where speed is critical. It isn't just for sorted arrays—it's the engine behind:

• Database Indexing: DBMS like PostgreSQL and MySQL use B-Tree structures (a generalization of binary search) to locate records in milliseconds, even among millions of rows.
• Java Collections: The Arrays.binarySearch() and Collections.binarySearch() methods underpin efficient lookups in standard Java libraries.
• Machine Learning: Algorithms like k-Nearest Neighbors (kNN) use binary search on sorted feature vectors to find optimal split points or nearest neighbors quickly.
• Autocomplete Systems: Searching through sorted dictionaries to find prefix matches efficiently.
• Debugging: "Git bisect" uses binary search logic to identify exactly which commit introduced a bug in your codebase.

Advantages & Limitations

Why use Binary Search?

• Speed: O(log n) is exponentially faster than linear search. For 1 million elements, binary search takes ~20 comparisons; linear search takes up to 1 million.
• Space: The iterative version requires no extra memory (O(1) space).
• Predictability: Performance is consistent even as data scales massively.

Constraints to Keep in Mind:

• Requires Sorting: The array must be sorted first. If you need to search a list only once, the cost of sorting (O(n log n)) outweighs the search benefit.
• Random Access Needed: Works best on data structures like arrays or ArrayLists that support O(1) access by index. It performs poorly on LinkedLists.
• Static Data Preference: Best suited for datasets that don't change often, as maintaining sorted order during frequent insertions/deletions adds overhead.

Read more: 7 Best-Paying Tech Skills Companies Are Hiring for Now

Common Mistakes in Java Binary Search

Even experienced developers trip up on these implementation details. Watch out for:

1. Integer Overflow: Calculating mid = (low + high) / 2 can overflow if low + high exceeds Integer.MAX_VALUE.
   • Fix: Always use mid = low + (high - low) / 2.
2. Unsorted Arrays: Passing an unsorted array to binary search yields unpredictable (and usually incorrect) results.
   • Fix: Ensure Arrays.sort(arr) is called before searching.
3. Off-by-One Errors: Confusing < with <= in loops or setting boundaries incorrectly (e.g., high = mid vs high = mid - 1).
   • Fix: Follow the standard template: while (low <= high) and strict boundary updates (mid + 1, mid - 1).
4. Not Handling "Not Found": Forgetting to define a return value for missing targets.
   • Fix: Return -1 or the insertion point (-insertionPoint - 1) to signal the element isn't there.
5. Recursive Stack Depth: Assuming recursion is free.
   • Fix: Be mindful of stack depth on constrained environments, though typically not an issue for binary search given log n grows very slowly.

Building production-grade search systems or optimizing performance-critical code? Hire experienced Java developers who understand algorithms deeply and can implement efficient solutions at scale.

Master Binary Search for Your Java Projects

Binary search in Java is a fundamental algorithm that every developer should master. With O(log n) time complexity, it's exponentially faster than linear search for sorted data—a difference that becomes critical when working with large-scale applications, database systems, or performance-sensitive code.

Key takeaways from this guide:

• Use iterative binary search for production code (O(1) space complexity)
• Use recursive binary search when code clarity matters more than memory
• Leverage Arrays.binarySearch() for standard use cases in Java
• Always verify your array is sorted before applying binary search
• Practice binary search variations for technical interviews

The binary search algorithm extends beyond simple array lookups. Understanding its divide-and-conquer principle enables you to solve complex problems like finding boundaries in sorted data, searching rotated arrays, and implementing efficient numerical algorithms.

Common mistakes to avoid in binary search Java code:

• Integer overflow when calculating mid: Use mid = left + (right - left) / 2 instead of mid = (left + right) / 2
• Incorrect loop termination: Use left <= right, not left < right
• Forgetting to sort the array before searching
• Off-by-one errors when adjusting left and right pointers

Ready to level up your algorithmic thinking? Hire experienced Java developers from Index.dev's global network—professionals who understand algorithms at this level and can optimize your codebase for performance and scale.

Or are you eager to advance your problem-solving skills to the next level? If you are a senior software developer interested in working remotely for high-end projects in the USA, UK, or Europe, register on Index.dev. Get matched with top companies on full-time, long-term engagements. 

Read more: 10 Programming Languages that Will Land You a Salary of $100k in the US