Binary Search in Java – Concept and Implementation
Basics of Python
5 Hrs. duration
9 Modules
1800+ Learners
Start Learning
Have you ever tried to find an item you need among a huge list of items? Perhaps you have a sorted list of numbers and want to locate one of them as fast as feasible. In this process, we have experienced multiple times that the linear search method is very slow because it goes through each element.
Well, the binary search comes to the rescue, then.
It is a technique that provides an even quicker solution. This algorithm halves the size of the search with each step and is far more efficient than the linear search. But this only works if the list is sorted.
Now, let’s understand the process of binary search in Java and how it can help us save time.
Detailed Algorithm Explanation for Binary Search in Java
Binary search works by successively halving the search interval. Here’s a step-by-step breakdown of how it works:
Start with two pointers, one at the beginning (left) and one at the end (right) of the array.
Find the middle element (mid).
Compare the middle element with the target value.
If the target value matches the middle element, you’re done.
If the target value is smaller, focus on the left half.
If the target value is larger, focus on the right half.
Repeat this process until the target value is found or the interval is empty.
Let’s look at a simple pseudocode:
Initialize left = 0 and right = array.length – 1.
While the left is less than or equal to the right:
Calculate mid = left + (right-left) / 2.
If array[mid] equals the target, return mid.
If array[mid] is less than the target, set left = mid + 1.
If array[mid] is greater, set right = mid – 1.
If the target is not found, return -1.
In this pseudocode, we can clearly see that the algorithm ensures that the search space is halved with each step. This makes the search process much faster than linear search.
Binary Search: Iterative Implementation in Java
Alright! Let’s look at how to create a binary search algorithm iteratively in Java. We’ll utilise a loop to split the search space in half continually. The process will be continued until the target element is discovered or the search space is consumed.
import java.util.Scanner;
public class BinarySearchIterative {
public int binarySearch(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;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Target not found
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] arr = {1, 3, 5, 7, 9, 11};
System.out.println("Enter the target element:");
int target = scanner.nextInt();
BinarySearchIterative bs = new BinarySearchIterative();
int result = bs.binarySearch(arr, target);
if(result != -1) {
System.out.println("Element found at index: " + result);
} else {
System.out.println("Element not found");
}
scanner.close();
}
}
Output:
Have issues understanding how this binary search in Java code worked and gave the output? Let’s see the explanation:
We start by defining the binarySearch method.
We set left and right to the start and end of the array.
Inside a loop, we calculate the midpoint.
If the mid element is the target, we return the index.
If the mid element is less than the target, we shift the left pointer.
If the mid element is greater, we shift the right pointer.
If the loop ends without finding the target, we return -1.
Output:
Example Input: Enter the target element: 7
Example Output: Element found at index: 3
Using this iterative method, we can quickly find an element in a sorted array, even if it’s large.
When working with sorted lists, have you ever wondered if there’s a more elegant way to search than using loops? That’s where the recursive approach to binary search in Java comes in.
Just like the iterative method, the recursive binary search splits the search space in half each step. But instead of using loops, we use function calls.
Here’s the code for a recursive binary search in Java:
import java.util.Scanner;
public class BinarySearchRecursive {
public int binarySearch(int[] arr, int left, int right, int target) {
if (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
return binarySearch(arr, mid + 1, right, target);
} else {
return binarySearch(arr, left, mid - 1, target);
}
}
return -1; // Target not found
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] arr = {1, 3, 5, 7, 9, 11};
System.out.println("Enter the target element:");
int target = scanner.nextInt();
BinarySearchRecursive bs = new BinarySearchRecursive();
int result = bs.binarySearch(arr, 0, arr.length - 1, target);
if(result != -1) {
System.out.println("Element found at index: " + result);
} else {
System.out.println("Element not found");
}
scanner.close();
}
}
Output:
Let’s quickly go through how this code executed and gave us the output:
The method binarySearch takes the array, left and right pointers, and the target value.
We calculate the middle point and compare it with the target.
If the middle element is the target, we return the index.
If the middle element is less than the target, we call the function recursively with the right half.
If the middle element is greater, we call the function recursively with the left half.
If the target isn’t found, we return -1.
Output:
Example Input: Enter the target element: 5
Example Output: Element found at index: 2
This recursive method is clean and simple. It’s a great way to use recursion in your search algorithms.
Using Java’s Built-In Arrays.binarySearch() Method
Sometimes, we want to avoid writing our own search functions and use built-in methods instead. Java provides a convenient Arrays.binarySearch() method that makes searching a breeze.
Here’s how you can use Arrays.binarySearch() in Java:
import java.util.Arrays;
import java.util.Scanner;
public class BinarySearchBuiltIn {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] arr = {5, 3, 9, 1, 7};
Arrays.sort(arr); // Ensure the array is sorted
System.out.println("Enter the target element:");
int target = scanner.nextInt();
int result = Arrays.binarySearch(arr, target);
if(result >= 0) {
System.out.println("Element found at index: " + result);
} else {
System.out.println("Element not found");
}
scanner.close();
}
}
Output:
Here is an explanation of this code to make it easy to understand for you:
We sort the array using Arrays.sort(arr) to ensure it’s in order.
We call Arrays.binarySearch(arr, target) to find the target element.
If the element is found, it returns the index; otherwise, it returns a negative value.
Output:
Example Input: Enter the target element: 7
Example Output: Element found at index: 3
This built-in method is efficient and easy to use, perfect for quick searches in sorted arrays.
Implementing Binary Search with Collections.binarySearch()
If you prefer working with lists, Java’s Collections.binarySearch() is your friend. It works similarly to Arrays.binarySearch() but for lists instead of arrays.
Here’s how you can use Collections.binarySearch() in Java:
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class BinarySearchCollections {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
List<Integer> list = new ArrayList<>();
list.add(5);
list.add(3);
list.add(9);
list.add(1);
list.add(7);
Collections.sort(list); // Ensure the list is sorted
System.out.println("Enter the target element:");
int target = scanner.nextInt();
int result = Collections.binarySearch(list, target);
if(result >= 0) {
System.out.println("Element found at index: " + result);
} else {
System.out.println("Element not found");
}
scanner.close();
}
}
Output:
Here’s a detailed explanation of this code for your better understanding:
We create a list and add some elements.
We sort the list using Collections.sort(list).
We call Collections.binarySearch(list, target) to find the target element.
If the element is found, it returns the index; otherwise, it returns a negative value.
Output:
Example Input: Enter the target element: 7
Example Output: Element found at index: 4
This method is very convenient for working with lists, and it’s just as efficient as Arrays.binarySearch().
Time and Space Complexity Analysis of Binary Search
Wondering how efficient binary search in Java is?
When dealing with large datasets, efficiency is key, and binary search stands out in terms of performance.
Let’s break down its time and space complexity.
Time Complexity
Binary search in Java is very fast. Its time complexity is O(log N), where N is the number of elements in the array.
But do you know why it is so fast? Well, here are the reasons:
Every step cuts the search space in half.
With each comparison, you eliminate half of the remaining elements.
This logarithmic reduction makes binary search significantly quicker than linear search, which has O(N) complexity.
Space Complexity
The space complexity depends on the implementation.
Iterative Binary Search: This method uses a constant amount of extra space. The space complexity is O(1).
Recursive Binary Search: This method can use more space due to the function call stack. The space complexity is O(log N) because each recursive call adds a new frame to the stack.
In both cases, binary search is efficient in terms of both time and space.
Conclusion
Binary search in Java is a sophisticated and efficient technique for finding a specific member in a sorted array or list. Binary search, whether performed iteratively, recursively, or utilising built-in Java methods, finds an element substantially faster than linear search.
The time and space complexity also explains how a binary search algorithm is better than a linear search algorithm. By understanding and implementing binary search, you can optimise your search operations and handle large datasets with ease.
FAQs
What is the primary requirement for binary search to work correctly?
The array or list must be sorted in ascending order.
Can binary search be used on data structures other than arrays and lists?
Yes, binary search can be adapted for use on other sorted data structures, such as trees and some databases.
How does Arrays.binarySearch() differ from Collections.binarySearch()?
binarySearch() works directly with arrays, but Collections.binarySearch() works with List objects and employs an iterator-based method for non-random access lists.
What are the differences between iterative and recursive binary search implementations?
The iterative implementation uses a loop to repeatedly divide the search interval, while the recursive implementation calls itself with updated intervals.
Deploying Applications Over the Cloud Using Jenkins
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.
