In this tutorial, I will show you how to implement binary search in Java to find an element in a sorted array. Binary search is one of the most important searching algorithms and a commonly asked question in Java coding interviews.
Unlike linear search, which examines elements one by one, binary search repeatedly divides the search range into two halves. This makes it significantly faster when searching large sorted arrays.
For example, suppose you have a sorted array containing thousands of numbers. Instead of checking every element, binary search compares the target with the middle element and eliminates half of the remaining elements after each comparison.
In this tutorial, you will learn how binary search works, how to implement it using iterative and recursive approaches, and how to use Java's built-in Arrays.binarySearch() method. I will also explain the algorithm with a dry run, time complexity analysis, and practical examples.
1. What Is Binary Search?
Binary search is an efficient searching algorithm used to find the position of a target element in a sorted collection.
It works by comparing the target element with the middle element of the current search range.
- If the target equals the middle element, the search is successful.
- If the target is smaller, continue searching in the left half.
- If the target is larger, continue searching in the right half.
- Repeat until the target is found or the search range becomes empty.
Important: The array must be sorted in ascending order for the implementations in this tutorial to work correctly.
2. Problem Statement
Write a Java program to search for a target element in a sorted integer array using the binary search algorithm.
If the target exists, return its index. Otherwise, return -1.
Example 1: Element Found
Input: arr = [10, 20, 30, 40, 50, 60, 70] target = 50 Output: Element found at index: 4
Explanation: The target element 50 is present at index 4. Java arrays use zero-based indexing.
Example 2: Element Not Found
Input: arr = [10, 20, 30, 40, 50, 60, 70] target = 45 Output: Element not found
The element 45 does not exist in the array, so the method returns -1.
3. Method 1: Binary Search Using an Iterative Approach
The iterative approach uses a while loop to repeatedly reduce the search range.
It maintains two pointers:
leftrepresents the beginning of the current search range.rightrepresents the end of the current search range.
During each iteration, the algorithm calculates the middle index and compares the corresponding element with the target.
Java Program Using Iterative Binary Search
public class BinarySearchExample {
/**
* Searches for a target in a sorted array.
*
* @param arr sorted integer array
* @param target element to find
* @return index of target, or -1 if not found
*/
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
// Calculate the middle index safely
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
// Search in the right half
left = mid + 1;
} else {
// Search in the left half
right = mid - 1;
}
}
// Target is not present
return -1;
}
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50, 60, 70};
int target = 50;
int result = binarySearch(arr, target);
if (result == -1) {
System.out.println("Element not found");
} else {
System.out.println(
"Element found at index: " + result);
}
}
}Output
Element found at index: 4
4. Step-by-Step Explanation of the Iterative Program
Step 1: Initialize the Search Boundaries
int left = 0;
int right = arr.length - 1;The left pointer starts at the first element, while right starts at the last element.
For an array containing seven elements, the initial search range is from index 0 to index 6.
Step 2: Continue While the Search Range Is Valid
while (left <= right) {The loop continues while at least one element remains in the search range.
If left becomes greater than right, the target is not present.
Step 3: Calculate the Middle Index
int mid = left + (right - left) / 2;This statement finds the middle index of the current search range.
Using left + (right - left) / 2 is preferable to (left + right) / 2 because adding two large indexes directly could cause integer overflow.
Step 4: Check Whether the Middle Element Matches
if (arr[mid] == target) {
return mid;
}If the middle element matches the target, return its index immediately.
Step 5: Search the Right Half
if (arr[mid] < target) {
left = mid + 1;
}If the middle element is smaller than the target, all elements at or before the middle position can be eliminated from the search.
The algorithm updates left to the position immediately after mid.
Step 6: Search the Left Half
else {
right = mid - 1;
}If the middle element is greater than the target, the algorithm eliminates the middle position and all elements to its right.
It then continues searching in the left half.
Step 7: Return -1 if the Element Is Missing
return -1;If the loop finishes without finding the target, the method returns -1.
5. Dry Run of Binary Search
Let's understand the algorithm using this example:
Array: [10, 20, 30, 40, 50, 60, 70] Index: 0 1 2 3 4 5 6 Target: 50
The algorithm begins with the complete array and repeatedly reduces the search range.
| Iteration | Left | Right | Mid | arr[mid] | Action |
|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 40 | 50 is greater than 40. Search right. |
| 2 | 4 | 6 | 5 | 60 | 50 is smaller than 60. Search left. |
| 3 | 4 | 4 | 4 | 50 | Target found at index 4. |
Final result:
Element found at index: 4
Notice that the algorithm finds the target in just three comparisons. It does not need to examine every element.
6. Method 2: Binary Search Using Recursion
Binary search can also be implemented using recursion.
Instead of using a loop, the recursive method calls itself with a smaller search range until it finds the target or reaches the base case.
Java Program Using Recursive Binary Search
public class RecursiveBinarySearch {
public static int binarySearch(
int[] arr, int left, int right, int target) {
// Base case: target is not present
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
// Target found
if (arr[mid] == target) {
return mid;
}
// Search the right half
if (arr[mid] < target) {
return binarySearch(
arr, mid + 1, right, target);
}
// Search the left half
return binarySearch(
arr, left, mid - 1, target);
}
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50, 60, 70};
int target = 30;
int result = binarySearch(
arr, 0, arr.length - 1, target);
if (result == -1) {
System.out.println("Element not found");
} else {
System.out.println(
"Element found at index: " + result);
}
}
}Output
Element found at index: 2
How Recursive Binary Search Works
- Check whether the search range is empty.
- Calculate the middle index.
- If the middle element matches the target, return its index.
- If the target is larger, recursively search the right half.
- Otherwise, recursively search the left half.
The recursive approach follows the same search logic as the iterative implementation.
However, each recursive call uses stack memory, making it less space-efficient than the iterative approach.
7. Method 3: Binary Search Using Arrays.binarySearch()
Java provides a built-in binary search method in the java.util.Arrays class.
You can use this method when you need to search a sorted array without implementing the algorithm yourself.
Java Program Using Arrays.binarySearch()
import java.util.Arrays;
public class BuiltInBinarySearch {
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50, 60, 70};
int target = 40;
int result = Arrays.binarySearch(arr, target);
if (result >= 0) {
System.out.println(
"Element found at index: " + result);
} else {
System.out.println("Element not found");
}
}
}Output
Element found at index: 3
Important: Understanding the Return Value
The built-in Arrays.binarySearch() method has slightly different return behavior from the custom methods shown earlier.
- If the target is found, it returns an index greater than or equal to zero.
- If the target is not found, it returns a negative value calculated using the insertion point.
Specifically, the return value for a missing target is:
-(insertion point) - 1
The insertion point is the index at which the target would need to be inserted to maintain sorted order.
For example:
Array: [10, 20, 30, 40, 50] Target: 25 Insertion point: 2 Return value: -3
Therefore, when checking whether an element exists, use result >= 0 rather than checking only for -1.
8. Time and Space Complexity
All three approaches use binary search, but their memory requirements differ.
| Approach | Time Complexity | Auxiliary Space |
|---|---|---|
| Iterative binary search | O(log n) | O(1) |
| Recursive binary search | O(log n) | O(log n) |
| Arrays.binarySearch() | O(log n) | O(1) |
Best-Case Time Complexity: O(1)
If the middle element matches the target during the first comparison, binary search finds it immediately.
Worst-Case Time Complexity: O(log n)
In the worst case, the algorithm repeatedly halves the search range until it finds the target or determines that the target is missing.
For example, a sorted array containing 1,024 elements requires at most 11 middle-element comparisons using the standard binary search loop.
Space Complexity
The iterative implementation uses only a few integer variables, so its auxiliary space complexity is O(1).
The recursive implementation uses additional call-stack space proportional to the recursion depth, giving it O(log n) auxiliary space complexity.
9. Binary Search vs. Linear Search
Binary search is generally faster than linear search for large sorted arrays.
| Feature | Linear Search | Binary Search |
|---|---|---|
| Input requirement | Works with sorted or unsorted arrays | Requires sorted data |
| Search strategy | Checks elements sequentially | Eliminates half the search range |
| Worst-case time | O(n) | O(log n) |
| Implementation | Very simple | Requires boundary management |
| Best use case | Small or unsorted arrays | Large sorted arrays |
10. Handling Important Edge Cases
Case 1: Target Is the First Element
Array: [5, 10, 15, 20, 25] Target: 5 Result: 0
Case 2: Target Is the Last Element
Array: [5, 10, 15, 20, 25] Target: 25 Result: 4
Case 3: Target Is Not Present
Array: [5, 10, 15, 20, 25] Target: 17 Result: -1
This result applies to the custom iterative and recursive implementations.
Case 4: Array Is Empty
Array: [] Target: 10 Result: -1
The iterative loop never executes because the initial right value is -1.
Case 5: Array Contains a Single Element
Array: [42] Target: 42 Result: 0
Case 6: Array Contains Duplicate Values
Array: [10, 20, 20, 20, 30] Target: 20 Result: Any matching index
Binary search can find an occurrence of a duplicate value, but the standard algorithm does not guarantee that it returns the first or last occurrence.
If you need the first or last occurrence, modify the algorithm to continue searching in the appropriate half after finding a match.
Case 7: Array Contains Negative Numbers
Array: [-20, -10, -5, 0, 10] Target: -5 Result: 2
Binary search works with negative integers as long as the array is sorted correctly.
11. Common Mistakes in Binary Search
Mistake 1: Performing Binary Search on an Unsorted Array
Binary search relies on sorted data.
For example, applying the standard algorithm directly to [40, 10, 50, 20, 30] may produce an incorrect result.
Make sure the array is sorted before searching.
Mistake 2: Using the Wrong Loop Condition
For an inclusive search range, use:
while (left <= right)Using only left < right can skip the final remaining element.
Mistake 3: Incorrectly Updating Search Boundaries
When searching the right half, use:
left = mid + 1;When searching the left half, use:
right = mid - 1;Setting a boundary to mid without properly changing the search range can cause an infinite loop.
Mistake 4: Calculating the Middle Index Unsafely
Avoid relying on:
int mid = (left + right) / 2;Instead, use:
int mid = left + (right - left) / 2;The second form avoids potential overflow when the indexes are large.
Mistake 5: Misinterpreting Arrays.binarySearch() Results
Unlike the custom methods, Arrays.binarySearch() does not always return -1 when an element is missing.
Always test whether the result is negative to determine whether the search failed.
12. Frequently Asked Questions
Q1. What is binary search in Java?
Binary search is a searching algorithm that finds an element in a sorted array by repeatedly dividing the search range into two halves.
Q2. What is the time complexity of binary search?
Binary search takes O(log n) time in the worst case and O(1) time in the best case.
Q3. Is binary search faster than linear search?
For large sorted arrays, binary search is generally faster because it eliminates half the remaining search range after each comparison. Linear search may need to examine every element.
Q4. Can binary search work on an unsorted array?
No. Standard binary search requires sorted data. For an unsorted array, sort it first or use another searching method.
Q5. Which is better: iterative or recursive binary search?
Both approaches have O(log n) time complexity. However, iterative binary search uses O(1) auxiliary space, while the recursive version uses O(log n) call-stack space.
Q6. Does binary search work with duplicate elements?
Yes. However, the standard implementation does not guarantee the first or last index when duplicate values exist.
Q7. Can binary search find the insertion position of a missing element?
Yes. Java's Arrays.binarySearch() method encodes the insertion position in its negative return value.
Q8. What happens if the array is null?
The examples assume a non-null array. Passing null results in a NullPointerException. Add explicit validation if your application must handle null inputs.
13. Conclusion
In this tutorial, you learned how to perform binary search on a sorted array in Java using three different approaches.
- Iterative binary search: Uses a loop and requires constant auxiliary space.
- Recursive binary search: Uses recursive calls to search smaller portions of the array.
- Arrays.binarySearch(): Uses Java's built-in binary search implementation.
For Java coding interviews, I recommend learning the iterative approach first. It is efficient, uses O(1) auxiliary space, and helps you understand how binary search updates its search boundaries.
Once you understand this algorithm, you can use the same technique to solve more advanced interview problems, including finding the first or last occurrence of a number, searching for insertion positions, and searching rotated sorted arrays.
14. Official Java Documentation
For more information about Java's built-in searching and array utilities, refer to the official Oracle documentation:
- Java Arrays Class — Includes the
Arrays.binarySearch()andArrays.sort()methods. - Java Collections Class — Includes binary search support for sorted lists.
- Java Language Specification: Arrays — Explains array types and array behavior in Java.
Continue Learning with Java Guides
Want to take your programming skills to the next level? Explore my practical Udemy courses on Java, Spring Boot, Microservices, Full-Stack Development, Docker, and Generative AI. You can also follow my structured learning roadmaps to become a professional developer.
By Ramesh Fadatare - Udemy Instructor Partner
Comments
Post a Comment
Leave Comment