Binary Search in Java
Master the fundamental concept of binary search in Java with our comprehensive article. Learn how to efficiently sort and search data, understand the logic behind it, and apply it in your coding practices.
In this article, we will discuss the binary search algorithm in Java. We will discuss various ways by which we can implement binary search with the space and time complexity of the code.
The binary search algorithm searches a targeted value or key in a Collection. This algorithm uses the divide and conquer technique to search for a key or value. In the divide and conquer technique, we solve the bigger problems by breaking them into smaller sub-problems. Solutions of smaller sub-problems combine to solve the big problem.
Must Check: Top Free Online Java Courses and Certifications
Must Check: Top Online Java Courses and Certifications
Note: The Collection on which we are applying binary search must be sorted.
Steps to perform a Binary Search
- Sort the Collection in ascending order.
- Set the start index to the first element and the end index to the last element.
- Set the middle element to the average of the start and end indices.
- Return the middle element if the target element is the middle element.
- If the target element is less than the middle element, set the end index to the middle one – 1.
- If the target element is greater than the middle element, set the start index to the middle index + 1.
- Repeat steps 3 to 6 until the element is found or the element is clearly not present in the Collection.
Let’s take an example using an array and perform these above steps to search an element using binary search.
Example: We have to take an unsorted array with zero indexing.
Now follow the steps mentioned to search for a value or key using binary search. Let’s a key is 5, which we have to search now, and we determine at which index the five is present in the array using binary search.
Steps:
- Sort the Array
- Initialize start and end index as:
- middle = (0+6)/2=3, and at middle index element is 6.
- The target element is 5, which is less than the middle element then end = middle – 1 = 2;
- Now start = 0 and end = 2, so middle = (0 + 2)/2 = 1.
- At index 1, an element is 4. Now, the target element 5 is greater than 4 so set start = middle + 1 = 2;
- Now at middle = 2, we get 5.
In this way, binary search works using the divide and conquer technique. Let’s understand this binary search using code.
Three ways to perform Binary Search in Java
Using Recursive Approach
In the program, we make a static method binarySearch(), which takes a sorted array, starting index, ending index, and the target key as the arguments. We use binary search steps using the recursive call of the binarySearch() method.
Code:
public class Main { public static int binarySearch(int[] array,int start,int end,int target) { if(end>=start) { int mid=start+(end-start)/2; if(array[mid]==target) { return mid; } if(array[mid]<target) { return binarySearch(array,mid+1,end,target); }else if(array[mid]>target) { return binarySearch(array,start,mid-1,target); } } return -1; }
public static void main(String[] args) { int[] array= {3,4,5,6,7,8,9}; int start=0; int end=array.length; int target=5; int index_of_target_element=binarySearch(array,start,end,target); System.out.println("Element 5 is present at:"+index_of_target_element);
}
}
Output:
Time Complexity: O(log n)
Space Complexity: O(log n)
Also Read: What is Java?
Using Iterative Approach
In the program, we make a static method binarySearch(), which takes a sorted array, starting index, ending index, and the target key as the arguments. We use a while loop for iteration by using starting and ending index of the array. Find the middle index and compare the value of the middle index; if it is equal to the target key, then the method returns the index of the target.
Code:
public class Main { public static int binarySearch(int[] array,int start,int end,int target) { while(start<=end) { int mid= start+ (end-start)/2; if(array[mid]==target) { return mid; } if(array[mid]<target) { start=mid+1; } if(array[mid]>target) { end=mid; } } return -1; }
public static void main(String[] args) { int[] array= {3,4,5,6,7,8,9}; int start=0; int end=array.length-1; int target=5; int index_of_target_element=binarySearch(array,start,end,target); System.out.println("Element 5 is present at:"+index_of_target_element);
}
}
Output:
Time Complexity: O(log n)
Space Complexity: 1
Using Arrays.binarySearch() method
In the program, we use the binarySearch() method of the array to get the index of the target key by passing a sorted array and target key.
Code:
import java.util.Arrays;
public class Main { public static void main(String[] args) { int[] array= {3,4,5,6,7,8,9}; int target=5; int answerIndex=Arrays.binarySearch(array, target); if(answerIndex<0) { System.out.println("Element is not found in the array"); } else { System.out.println("Element 5 is present at:"+ answerIndex); }
}
}
Output:
Contributed By: Shubham Kumar
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
