Binary Search Program in Java

Last Updated on April 18, 2023 by Prepbytes

Searching is one of the most fundamental operations in computer science. It involves finding a specific element from a given data set. There are several search algorithms available, and one of the most efficient and widely used algorithms is the Binary search algorithm. In this article, we will discuss Binary Search in Java, its logic, and its implementation.

The Logic of Binary Search in Java

The logic of binary search in Java is to search for an element in a sorted array by repeatedly dividing the search interval in half. The algorithm starts by comparing the element to be searched with the middle element of the array. If the element matches the middle element, the search is successful, and the index of the middle element is returned.

If the element is less than the middle element, the search is continued in the left half of the array, as the element can only be present in that half. If the element is greater than the middle element, the search is continued in the right half of the array, as the element can only be present in that half.

The search interval is again divided in half, and the process continues until the element is found or until the search interval becomes empty.

The key idea behind binary search is to reduce the search space by half at every step of the algorithm. This reduces the number of comparisons required to find the element, making the search more efficient. The time complexity of the binary search is O(log n), where n is the number of elements in the array.

Binary Search in Java Explanation

Item to be searched=20
input:

beg=0, end=4, mid=2

beg=3, end=4, mid=3

Element found at index 3, Hence 3 will get returned.

Algorithm of Binary search in Java

The general steps for both methods (iterative and recursive) are discussed below:

• Step 1 – Read the user’s search element.
• Step 2 – Initialize the lower and upper bounds of the search interval. For the iterative method, this is done using two variables l and r, whereas, for the recursive method, this is done by passing the bounds as arguments to the function.
• Step 3 – Find the middle element of the search interval by calculating the average of the lower and upper bounds. For the iterative method, this is done using the formula m = l + (r – l) / 2, whereas for the recursive method, this is done inside the function by calculating mid = l + (r – l) / 2.
• Step 4 – Compare the middle element with the element to be searched. If they are equal, return the index of the middle element.
• Step 5 – If the element is less than the middle element, then the search continues in the left half of the array. For the iterative method, this is done by updating the upper bound to r = m – 1, whereas, for the recursive method, this is done by making a recursive call to the function with the same lower bound and a new upper bound of m – 1.
• Step 6 – If the element is greater than the middle element, then the search continues in the right half of the array. For the iterative method, this is done by updating the lower bound to l = m + 1, whereas, for the recursive method, this is done by making a recursive call to the function with the same upper bound and a new lower bound of m + 1.
• Step 7 – Repeat steps 3-6 until the element is found or the search interval is empty.
• Step 8 – If the element is not found in the array, return -1 and display "Element is not found in the array!!!".

Pseudo Code for Both the Logics (Recursive and Iterative)

Iteration Method of Binary Search in Java
do until the pointers low and high meet each other.

    mid = (low + high)/2
    if (x == arr[mid])
        return mid
    else if (x > arr[mid]) // x is on the right side
        low = mid + 1
    else                       // x is on the left side
        high = mid - 1

Recursive Method of Binary Search in Java
binarySearch(arr, x, low, high)

    if high >= low
        mid = (low + high) / 2 
        if x == arr[mid]
            return mid
        else if x > arr[mid]        // x is on the right side
            return binarySearch(arr, x, mid + 1, high)
        else                               // x is on the right side
            return binarySearch(arr, x, low, mid - 1)
    return -1

Program for Binary Search in Java Using Recursive Approach

Below is the code implementation and explanation of the program for Binary Search in Java using the recursive approach:

import java.util.*;
class PrepBytes {
	int binarySearch(int arr[], int l, int r, int x)
	{
		if (r >= l && l <= arr.length - 1) {
			int mid = l + (r - l) / 2;
			if (arr[mid] == x)
				return mid;				
			if (arr[mid] > x)
				return binarySearch(arr, l, mid - 1, x);
			return binarySearch(arr, mid + 1, r, x);
		}
		return -1;
	}
	public static void main(String args[])
	{
		PrepBytes ob = new PrepBytes();
		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);
	}
}

Output

Element found at index 3

Explanation: The above code is the implementation of Binary Search in Java. The class "PrepBytes" contains a method "binarySearch". The binary search method first checks if the starting index "l" is less than or equal to the ending index "r" and if the starting index "l" is less than or equal to the length of the array "arr". If not, it returns -1 indicating that the element is not present in the array.

If the above condition is true, it calculates the mid index using the formula (l + r) / 2. It then checks if the element at the mid index is equal to the element to be searched "x". If it is, it returns the mid-index.

If the element at the mid index is greater than the element to be searched "x", it means that the element can only be present in the left half of the array. Therefore, the method calls itself recursively with the left half of the array.

If the element at the mid index is smaller than the element to be searched "x", it means that the element can only be present in the right half of the array. Therefore, the method calls itself recursively with the right half of the array.

Program for Binary Search in Java Using Iterative Approach

Below is the code implementation and explanation of the program for Binary Search in Java using the iterative approach:

class PrepBytes {

	int binarySearch(int arr[], int x)
	{

		int l = 0, r = arr.length - 1;

		while (l <= r) {
			int m = l + (r - l) / 2;
			if (arr[m] == x)
				return m;

			if (arr[m] < x)
				l = m + 1;
			else
				r = m - 1;
		}

		return -1;
	}

	public static void main(String args[])
	{

		PrepBytes ob = new PrepBytes();


		int arr[] = { 2, 3, 4, 10, 40 };
		int n = arr.length;
		int x = 10;
		int result = ob.binarySearch(arr, x);
		if (result == -1)
			System.out.println("Element not present");
		else
			System.out.println("Element found at index " + result);
	}
}

Output

Element is found at index 3

Explanation: The above code is an implementation of Binary Search in Java. The class "PrepBytes" contains a method "binarySearch". The binary search method first initializes two variables "l" and "r" to 0 and "arr.length – 1" respectively. It then enters into a while loop that executes until the value of "l" is less than or equal to the value of "r".

Inside the loop, the method calculates the mid index "m" using the formula (l + r) / 2. It then checks if the element at the mid index is equal to the element to be searched "x". If it is, it returns the mid-index.

If the element at the mid index is smaller than the element to be searched "x", it means that the element can only be present in the right half of the array. Therefore, the method updates the value of "l" to "m + 1".

If the element at the mid index is greater than the element to be searched "x", it means that the element can only be present in the left half of the array. Therefore, the method updates the value of "r" to "m – 1".

If the element is not found in the array, the while loop will terminate, and the method will return -1 indicating that the element is not present in the array.

Time Complexity for Binary Search in Java

Best Case Complexity – In a binary search, the best case scenario is when the searchable element is discovered in the first comparison, or when the first middle element is in fact the searchable element. Binary search has a best-case temporal complexity of O(1).

Average Case Complexity – For a binary search, the average case time complexity is O(logn).

Worst Case Complexity – The worst case scenario for binary search is when we have to continuously narrow the search space until there is just one element. Binary search has a worst-case temporal complexity of O(logn).

Space Complexity for Binary Search in Java

The Space complexity for coding binary search program in Java is O(1).

Tips: On sorted array elements, binary search can be applied. We must first sort the list elements if they are not already organized in a sorted fashion.

Conclusion
In conclusion, Binary Search is a highly efficient algorithm for searching a specific element in a sorted array. With its O(log n) time complexity, it is widely used in various computer science applications. Both recursive and iterative approaches can be used to implement Binary Search in Java, making it a versatile tool for developers.

FAQs

Here are some frequently asked questions on Binary Search in Java.

Q1: Can Binary Search be used for an unsorted array in Java?
Ans: No, Binary Search cannot be used for an unsorted array in Java. It only works with a sorted array.

Q2: What happens when the element to be searched is not present in the array in Java?
Ans: If the element to be searched is not present in the array, the Binary Search algorithm returns -1.

Q3: Is Binary Search faster than Linear Search in Java?
Ans: Yes, Binary Search is faster than Linear Search in Java for large datasets because of its O(log n) time complexity.

Q4: Can Binary Search be performed on a linked list in Java?
Ans: No, Binary Search cannot be performed on a linked list in Java because linked lists do not provide random access.

Q5: What is the advantage of using the recursive approach in Binary Search in Java?
Ans: The advantage of using the recursive approach in Binary Search in Java is that it is easy to understand and implement.

Q6: What is the advantage of using the iterative approach in Binary Search in Java?
Ans: The advantage of using the iterative approach in Binary Search in Java is that it is more efficient and faster than the recursive approach.

Q7: Can Binary Search be used for multidimensional arrays in Java?
Ans: No, Binary Search cannot be used for multidimensional arrays in Java because it only works for one-dimensional arrays.

Other Java Programs

Java Program to Add Two Numbers
Java Program to Check Prime Number
Java Program to Check Whether a Number is a Palindrome or Not
Java Program to Find the Factorial of a Number
Java Program to Reverse a Number
Java Program to search an element in a Linked List
Program to convert ArrayList to LinkedList in Java
Java Program to Reverse a linked list
Java Program to search an element in a Linked List
Anagram Program in Java
Inheritance Program in Java
Even Odd Program in Java
Hello World Program in Java
If else Program in Java