Methods for Java Binary Search
There are three methods in Java to implement Binary Search in Java are mentioned below:
- Iterative Method
- Recursive Method
- Inbuild Method
1. Iterative Method for Binary Search in Java
Below is the implementation is mentioned below:
Java
// Java implementation of iterative Binary Search class BinarySearch { // Returns index of x if it is present in arr[l....r], else return -1 int binarySearch( int arr[], int l, int r, int x) { while (l <= r) { int mid = (l + r) / 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 // so we decrease our r pointer to mid - 1 } else if (arr[mid] > x) { r = mid - 1 ; // Else the element can only be present // in right subarray // so we increase our l pointer to mid + 1 } else { l = mid + 1 ; } } // We reach here when element is not present // in array return - 1 ; } // Driver method to test above public static void main(String args[]) { BinarySearch ob = new BinarySearch(); int arr[] = { 2 , 3 , 4 , 10 , 40 }; int n = arr.length; int x = 10 ; int result = ob.binarySearch(arr, 0 , n - 1 , x); if (result == - 1 ) System.out.println( "Element not present" ); else System.out.println( "Element found at index " + result); } } |
Element found at index 3
Tip: Geeks you must be wondering out whether there is any function like lower_bound() or upper_bound() just likely found in C++ STL. so the straight answer is that there was no function only till Java 9, later onwards they were added.
2. Recursive Method for Binary Search
Below is the implementation of the above method:
Java
// Java implementation of // recursive Binary Search // Driver Class class BinarySearch { // Returns index of x if it is present in arr[l.. // r], else return -1 int binarySearch( int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 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, l, mid - 1 , x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1 , r, x); } // We reach here when element is not present // in array return - 1 ; } // main function public static void main(String args[]) { BinarySearch ob = new BinarySearch(); int arr[] = { 2 , 3 , 4 , 10 , 40 }; int n = arr.length; int x = 10 ; int result = ob.binarySearch(arr, 0 , n - 1 , x); if (result == - 1 ) System.out.println( "Element is not present in array" ); else System.out.println( "Element is present at index " + result); } } |
Element is present at index 3
Complexity of the above method
Time Complexity: O(log N)
Space Complexity: O(1), If the recursive call stack is considered then the auxiliary space will be O(log N)
3. In Build Method for Binary Search in Java
Arrays.binarysearch() works for arrays which can be of primitive data type also.
Below is the implementation of the above method:
Java
// Java Program to demonstrate working of binarySearch() // Method of Arrays class In a sorted array // Importing required classes import java.util.Arrays; // Main class public class GFG { // Main driver method public static void main(String[] args) { // Declaring an integer array int arr[] = { 10 , 20 , 15 , 22 , 35 }; // Sorting the above array // using sort() method of Arrays class Arrays.sort(arr); int key = 22 ; int res = Arrays.binarySearch(arr, key); if (res >= 0 ) System.out.println( key + " found at index = " + res); else System.out.println(key + " Not found" ); key = 40 ; res = Arrays.binarySearch(arr, key); if (res >= 0 ) System.out.println( key + " found at index = " + res); else System.out.println(key + " Not found" ); } } |
22 found at index = 3 40 Not found
Binary Search in Java
Binary search is one of the searching techniques applied when the input is sorted here we are focusing on finding the middle element that acts as a reference frame whether to go left or right to it as the elements are already sorted. This searching helps in optimizing the search technique with every iteration is referred to as binary search and readers do stress over it as it is indirectly applied in solving questions.
Contact Us