Methods for Java Binary Search
- Recursive Method
- Iterative Method
- Inbuild Method
1. Recursive Method for Binary Search Java
Implementation of Recursive Binary Search Java:
// 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
2. Iterative Method for Binary Search Java
// 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
3. Implementation of Built-in Binary Search in Java
Java provides an in-built method for binary search in the java.util.Arrays class. The method Arrays.binarySearch() efficiently searches for a specific element in a sorted array and returns its index if found. If the element is not present, it returns a negative value indicating the insertion point.
Here’s the implementation:
import java.util.Arrays;
public class BinarySearchExample {
public static void main(String[] args) {
// Sorted array
int[] arr = {10, 20, 30, 40, 50, 60, 70};
// Element to search
int key = 40;
// Using Arrays.binarySearch()
int result = Arrays.binarySearch(arr, key);
// Output the result
if (result >= 0) {
System.out.println("Element " + key + " found at index: " + result);
} else {
System.out.println("Element " + key + " not found. Insertion point: " + (-result - 1));
}
}
}

You can also try this code with Online Java Compiler
Run CodeOutput
If the element exists in the array:
Element 40 found at index: 3
If the element does not exist in the array (e.g., key = 35):
Element 35 not found. Insertion point: 3
Time Complexity
The time complexity of the binary search is O(logN), where N is the size of the array.
Binary Search in Java Collections
Java Collections framework provides the Collections.binarySearch() method to perform binary search on a List. The list must be sorted in natural order or by a comparator for accurate results. The method returns the index of the element if found or a negative value indicating the insertion point.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BinarySearchInCollections {
public static void main(String[] args) {
// Sorted list
List<Integer> list = new ArrayList<>();
Collections.addAll(list, 10, 20, 30, 40, 50, 60, 70);
// Element to search
int key = 40;
// Using Collections.binarySearch()
int result = Collections.binarySearch(list, key);
// Output the result
if (result >= 0) {
System.out.println("Element " + key + " found at index: " + result);
} else {
System.out.println("Element " + key + " not found. Insertion point: " + (-result - 1));
}
}
}

You can also try this code with Online Java Compiler
Run CodeOutput
If the element exists:
Element 40 found at index: 3
If the element does not exist (e.g., key = 35):
Element 35 not found. Insertion point: 3
Frequently Asked Questions
What is a binary search in Java?
Binary search is an efficient algorithm in Java for finding the position of a target element in a sorted array or list. It works by repeatedly dividing the search interval in half until the target is found or the interval is empty.
What is the formula for binary search in Java?
The formula to find the middle index in binary search is:
mid = low + (high - low) / 2
This prevents integer overflow compared to using (low + high) / 2. Adjust low or high based on comparisons.
What is the main advantage of binary search in Java?
The main advantage of binary search is its efficiency, with a time complexity of O(log n). It significantly reduces the number of comparisons required compared to linear search, making it ideal for large, sorted datasets.
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
Binary search is a highly efficient algorithm for finding elements in sorted arrays or lists in Java. With a time complexity of O(log n), it outperforms linear search, especially for large datasets. By understanding the underlying mechanics and using built-in methods like Arrays.binarySearch() and Collections.binarySearch(), developers can optimize search operations in their Java projects.
Recommended problems:
Recommended Articles:`
- Iteration Statements in Java
- Duck Number in Java
- Hashcode Method in Java
- Swap Function in Java