Binary Search Program in Java

We’ll talk about the Binary Search Algorithm in this article. Finding a certain element in the list is the process of searching. The method is deemed successful and returns the element’s location if the element is present in the list. If not, the search is considered fruitless.

The 2 most used search methods are linear search & binary search. Here, we’ll discuss the Binary Search Algorithm.

The search strategy that performs well on sorted lists is binary search. Thus, we must ensure that now the list is sorted before using the binary search strategy to find an element in it.

In binary search, the item is compared to the list’s center element after being split into two halves, which is known as the divide and conquer approach. The location of the middle element is returned if a match is discovered. Otherwise, we examine any half, depending on how the game turns out.

For creating binary search program in C, there are two methods-

  • Recursive Method
  • Iterative Method

Binary Search Logic

The binary search is justified by the assumption that there is a key. This key stores the value to be searched.. The sum of the two values—the highest and lowest—is divided by two which will be the midpoint value. The array’s lowest and highest values will be its first and last element. The key is then compared to the midpoint value. If mid is the same as the key, we receive the output immediately. The operation is repeated on the condensed array if the key is greater than mid, in which case mid+1 becomes the lowest value. Otherwise, mid-1 becomes the greatest value and the process is repeated on the reduced array if the key value is smaller than mid. A not found notice is shown if it can’t be found anywhere.

Binary Search Explanation

Item to be searched=20
input:

0 1 2 3 4
10 11 16 20 23

beg=0, end=4, mid=2

0 1 2 3 4
10 11 16 20 23

beg=3, end=4, mid=3

0 1 2 3 4
10 11 16 20 23

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

Binary Search Algorithm

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

  1. Read the user’s search element.
  2. In the sorted array, locate the middle element.
  3. Comparing the middle element of the sorted array with the search element.
  4. If both are matched, the function will end and the message "Given element is found!!!" will be displayed.
  5. Check to see if the search element is smaller or larger than the middle element if neither of them match.
  6. Repeat steps 2, 3, 4, and 5 for the middle element’s left subarray if the search element is smaller than the middle element.
  7. Repeat steps 2, 3, 4, and 5 for the middle element’s right subarray if the search element is greater than it.
  8. Repeat this procedure until the array contains the search element or until the subarray contains only one element.
  9. If that element also doesn’t match with the search element, then display "Element is not found in the array!!!" and terminate the function.

Pseudo Code for Both the Logics (Recursive and Iterative)

Iteration Method
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
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

Java Code Program for Binary Search using Recursive

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

Java Code Program for Binary Search using Iterative

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

Time Complexity for Binary Search

Scenario Time Complexity
Best Case O(1)
Average Case O(logn)
Worst Case O(logn)

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

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
This blog has discussed the flow and implementation of both methods (iterative and recursive) for binary search program in Java. We hope this article helps you to enhance your knowledge and gives you a grasp to solve more similar problems. Also, you can visit PrepBytes for practicing more similar questions.

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

Leave a Reply

Your email address will not be published. Required fields are marked *