Binary Search in Java

by

Binary search is a powerful algorithm used to efficiently find a specific element in a sorted array or list. In Java, implementing binary search is straightforward and can significantly improve the performance of search operations on large datasets. In This article we going to implement binary search in Java.

Binary Search in Java

Binary Search: A Overview

The essence of binary search lies in exploiting the sorted nature of an array. The algorithm repeatedly divides the array into halves (divide and conquer approach), comparing the target element with the middle element of the current subarray. If the target element matches the middle element, the search is successful, and the index of the target element is returned. Otherwise, the search continues in the relevant half, narrowing down the search space with each iteration.

Implementing Binary Search in Java: A Step-by-Step Guide

Implementing the binary in Java involves defining a recursive method that takes the sorted array, the target element, and the starting and ending indices as parameters. The recursive method for binary search follows these steps:

  1. Base Case: If the starting index exceeds the ending index, indicating that the element is not present in the array, return -1.
  2. Calculate the Middle Index: Calculate the middle index of the current subarray.
  3. Comparison and Recursion: Compare the target element with the middle element. If they are equal, return the middle index, indicating the element’s position. Otherwise, if the target element is smaller, recursively call the method with the left subarray. If larger, recurse with the right subarray.

Now let’s write the code to implement binary search in Java

Binary Search in Java : Code


public class BinarySearch {
//    Java Binary Search Method
    public static int binarySearch(int[] array, int target) {
        int low = 0;
        int high = array.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (array[mid] == target) {
                return mid; // element found
            } else if (array[mid] < target) {
                low = mid + 1; // Discard left half of the array
            } else {
                high = mid - 1; // Discard right half of the array
            }
        }

        return -1; // Target not found
    }

    public static void main(String[] args) {
        
        int[] sortedArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int target = 7;

        int result = binarySearch(sortedArray, target);

        if (result != -1) {
            System.out.println("found at index: " + result);
        } else {
            System.out.println("not found");
        }
    }
}

Output

Binary Search in Java

Binary Search Time Complexity

The time complexity of binary search is O(log n), where n is the number of elements in the array. This logarithmic time complexity makes binary search highly efficient, especially when dealing with large datasets. The algorithm’s ability to quickly narrow down the search space by half in each iteration contributes to its outstanding performance. Developers can leverage this efficiency to optimize

search operations and improve the overall performance of their Java applications.

See Also

Leave a Comment