Binary Search Java

Binary search is an efficient algorithm used to search target element in a sorted array or a list. It follows the divide and conquer approach. It is faster than linear search. Note that an array or list must be sorted before performing the binary search. If we have an unsorted array or list, we can sort the array using the Arrays.sort(arr) method.

Working of Binary Search

1. Sorted Data Requirement: First, check if the given array or list is sorted in ascending order, or not. If not sorted, it must be sorted first.
2. Find the Middle Element: Find the middle element of the array or list to compare the target value.
3. Compare and Reduce:
   • If the target value matches the middle element, its position is found, and the search terminates.
   • If the target value is less than the middle element, the search continues in the left subarray.
   • If the target value is greater than the middle element, the search continues in the right subarray.
4. Repeat: Steps 2 and 3 are repeated on the new, reduced search space until the target value is found or the search space becomes empty (indicating the target is not present).

Binary Search Algorithm

Binary Search Example

Consider the following array. We have taken a sorted array in which we have to search for the value 28 (target element).

The target element is greater than the current mid element (i.e. 28). The search moves to the right subarray. In the right subarray, the middle element is 32, and the target element (28) is less than the middle element. So, the search moves to the right of the array. We found the target element. Stop the search.

Approaches for Binary Search

There are the following three ways to perform a binary search:

1. Iterative Approach
2. Recursive Approach
3. Using Arrays.binarySearch() Method

Binary Search Example

Let's implement binary search logic in a Java program.

Output:

Element found at index: 3

Binary Search Using the Iterative Approach

The Iterative Method for Binary Search in Java is a straightforward and efficient technique used to find the position of a target element in a sorted array. This approach uses a while loop to reduce the search range by half after each iteration, adjusting the start and end indices based on the comparison with the target value.

Output:

Element found at index: 4

Binary Search Using Recursion

The recursive approach splits the array in half during each call, narrowing down the search area by focusing on either the left or right segment based on the comparison with the midpoint value. The recursion continues until the target is found or the search space is empty, at which point the algorithm terminates.

Let's implement the recursive approach in a Java program.

Output:

Element is found at index: 2

Binary Search Using Arrays.binarySearch() Method

The Java Arrays class provides different variants of the binarySearch() method for byte, char, int, float, double, long, object, and short data types. It is a static method.

The method searches specified value using the binary search algorithm. The array must be sorted (as by the sort(int[]) method) prior to making this call. If it is not sorted, the results are undefined. If the array contains multiple elements with the specified value, there is no guarantee which one will be found.

Syntax:

The method takes two arguments, an array to be search for, and the element (key) to be searched for. When the target element is found, it returns the index value of the element; otherwise, it returns a negative value indicating the insertion point to keep the array sorted.

Output:

Element found at index: 4

Binary Search Using Collections.binarySearch() Method

The Java Collections class also provides the built-in binarySearch() method. The method searches for the specified object using the binary search algorithm. The list must be sorted in ascending order. If the list is not sorted, the results are undefined. If the list contains multiple elements equal to the specified object, there is no guarantee which one will be found. It simplifies searching operations in Java Collections, offering a standardized and optimized approach for locating elements.

Syntax:

The method accepts two parameters: the list to be search and the key element to be searched for. It returns the index value of the key element.

Output:

Element found at index: 5

Complexity Analysis

Time Complexity

In binary search, at each step, the algorithm divides the array by 2. After k steps, the size becomes n / 2^k. When we solve n / 2^k = 1, we get k = log₂(n).

Space Complexity