Binary Search Algorithm in Java

   Last Updated: 06 October, 2024       🕓  5 Mins

A search is the process of finding a specific element in a list. In this tutorial, we are going to talk about how to search for a specific element in a list using a binary search algorithm in Java.

What is a binary search algorithm?

The binary search algorithm is a technique for searching a specific element within a sorted list of elements. It uses the divide-and-conquer approach to rapidly find the specific element by repeatedly dividing the search space in half.

If the specific element is less than the middle element, it can't be in the right half of the data structure, so discard it and focus on the left half. Conversely, if the target element is greater, discard the left half and focus on the right half and continue this process of dividing and searching until we either find the target element or reach an empty sub-array, indicating the element is not present.

The binary search algorithm is powerful and efficient. It is achieving a time complexity of O(log n), where n is the total number of elements in the list. It is significantly faster than linear search (O(n)).

Binary search is implemented using following steps

• Step 1 - Read the search element from the user.
• Step 2 - Find the middle element in the sorted list.
• Step 3 - Compare the search element with the middle element in the sorted list.
• Step 4 - If both are matched, then display "Given element is found!!!" and terminate the function.
• Step 5 - If both are not matched, then check whether the search element is smaller or larger than the middle element.
• Step 6 - If the search element is smaller than middle element, repeat fw-bold 2, 3, 4 and 5 for the left sublist of the middle element.
• Step 7 - If the search element is larger than middle element, repeat fw-bold 2, 3, 4 and 5 for the right sublist of the middle element.
• Step 8 - Repeat the same process until we find the search element in the list or until sublist contains only one element.
• Step 9 - If that element also doesn't match with the search element, then display "Element is not found in the list!!!" and terminate the function.

Binary Search Implementation in Java

There are the following ways to implement binary search in Java:

• Iterative Implementation
• Recursive Implementation
• Using Arrays.binarySearch()
• Using Collections.binarySearch()

1. Iterative Implementation

class BinarySearchExample1 { // Returns index of key if it is present in array, else return -1 static int binarySearch(int arr[], int min, int max, int key) { while (min <= max) { int mid = (min + max) / 2; // If the element is present at the middle itself if (arr[mid] == key) { return mid; // If element is smaller than mid, then // it can only be present in left subarray // so we decrease our max pointer to mid - 1 } else if (arr[mid] > key) { max = mid - 1; // Else the element can only be present in right subarray // so we increase our min pointer to mid + 1 } else { min = mid + 1; } } // Return -1, if element is not present in array return -1; } // Driver method to test above public static void main(String args[]) { int array[] = { 10, 20, 30, 40, 50, 60, 70, 80 }; int max = array.length; int min = 0; // 1st Scenario, If key is present in the array int key = 40; int result = binarySearch(array, min, max - 1, key); if (result == -1) System.out.println("Element " + key + " is not present in array"); else System.out.println("Element " + key + " is present at index "+ result); // 2nd Scenario, If key is not available in the array key = 250; result = binarySearch(array, min, max - 1, key); if (result == -1) System.out.println("Element " + key + " is not present in array"); else System.out.println("Element " + key + " is present at index "+ result); } }

Output

Element 40 is present at the index 3
Element 250 is not present in array

2. Recursive Implementation

class BinarySearchExample2 { // Returns index of key if it is present in array, else return -1 static int recursiveBinarySearch(int array[], int min, int max, int key) { if (max >= min) { int mid = min + (max - min) / 2; // If the element is present at the middle itself if (array[mid] == key) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (array[mid] > key) return recursiveBinarySearch(array, min, mid - 1, key); // Else the element can only be present in right subarray return recursiveBinarySearch(array, mid + 1, max, key); } // Return -1, if element is not present in array return -1; } public static void main(String args[]) { int array[] = { 10, 20, 30, 40, 50, 60, 70, 80 }; int max = array.length; int min = 0; // 1st Scenario, If key is present in the array int key = 40; int result = recursiveBinarySearch(array, min, max - 1, key); if (result == -1) System.out.println("Element " + key + " is not present in array"); else System.out.println("Element " + key + " is present at index "+ result); // 2nd Scenario, If key is not available in the array key = 250; result = recursiveBinarySearch(array, min, max - 1, key); if (result == -1) System.out.println("Element " + key + " is not present in array"); else System.out.println("Element " + key + " is present at index "+ result); } }

Output

Element 40 is present at the index 3
Element 250 is not present in array

3. Using Arrays.binarySearch()

import java.util.Arrays; public class BinarySearchExample3 { public static void main(String[] args) { // Create an integer type array int array[] = { 50, 80, 10, 40, 60, 30, 70, 20 }; // Sort the array before doing binary search // using sort() method of java.util.Arrays class Arrays.sort(array); // 1st Scenario, If key is available in the array // Setting the key which is exist in the array int key = 60; int result = Arrays.binarySearch(array, key); if (result >= 0) System.out.println("The key: " + key + " found at index = " + result); else System.out.println("The key: " + key + " is not found in the array"); // 2nd Scenario, If key is not available in the array // Setting the different key which is not exist in the array key = 100; result = Arrays.binarySearch(array, key); if (result >= 0) System.out.println("The key: " + key + " found at index = " + result); else System.out.println("The key: " + key + " is not found in the array"); } }

Output

The key: 60 found at the index = 5
The key: 100 is not found in the array

4. Using Collections.binarySearch()

import java.util.ArrayList; import java.util.Collections; import java.util.List; public class BinarySearchExample4 { public static void main(String[] args) { // Creating an ArrayList of integer type List<Integer> list = new ArrayList<>(); // Adding values in the list list.add(10); list.add(20); list.add(30); list.add(40); list.add(50); // 1st Scenario, If key is available in the list // Setting the key which is exist in the list int key = 30; // Searches the specified list for the specified object using // the binary search algorithm int result = Collections.binarySearch(list, key); if (result >= 0) System.out.println("The key: " + key + " found at index = " + result); else System.out.println("The key: " + key + " is not found in the list"); // 2nd Scenario, If key is not available in the list // Setting the different key which is not exist in the list key = 90; result = Collections.binarySearch(list, key); if (result >= 0) System.out.println("The key: " + key + " found at index = " + result); else System.out.println("The key: " + key + " is not found in the list"); } }

Output

The key: 30 found at the index = 2
The key: 90 is not found in the list