Binary Search Algorithm in Java.

Given a sorted integer array arr[] of size n and a target element X, the task is to write a Java program to find and return the index of the target from the given array. Return -1 if the target element is not present in the array.

Example:

Input: arr[] = {1, 2, 3, 4, 5, 6, 8} X = 4
Output: Element found at index 3

Input: arr[] = {3, 5, 10, 11, 12} x = 6
Output: Element not found in the array

Binary search and Linear search are the two most popular search algorithms and binary search is more efficient because its time complexity is less than linear search. But the important thing to note is that binary search is only applicable to a sorted array. 

Binary Search Algorithm.

The Binary Search Algorithm is based on the idea of comparing the target value with the middle element of the array. If the target value is equal to the middle value of the array then searching is complete. If they are not equal and the target value is smaller than the middle value, we will continue searching on the left side of the array. If the target value is larger than the middle value, we will continue searching on the right side of the array. 

Steps for Binary Search Algorithm:

• Initialize the left and right pointer as low = 0, high = n-1. 

• While low <= high, compare the middle element arr[mid] of the array with target value x. 

• If the middle element matches with target arr[mid] = x, return the index of the middle element mid.

• If the target is less than the middle element arr[mid] > x, continue searching the left half. (high = mid - 1)

• If the target is larger than the middle element arr[mid] < x, continue searching the right half. (low = mid + 1)

• If the target element is not found, return -1.

Java Program for Binary Search Using Iteration.

// Java code to search the target element using binary search
public class BinarySearch {

    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1; // Element not found
    }

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

        int result = binarySearch(arr, target);

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

Output:

Element found at index 4

Time Complexity: Binary search has a time complexity of O(log n), where n is the number of elements in the array. This is because, with each comparison, the size of the remaining array is halved.

Space Complexity: Binary search has a space complexity of O(1). It doesn't require additional memory that scales with the size of the input.

Java Program for Binary Search Using Recursion.

// Java code for Binary Search to target element using Recursion
public class BinarySearch {

    public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
        if (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                return binarySearchRecursive(arr, target, mid + 1, right);
            } else {
                return binarySearchRecursive(arr, target, left, mid - 1);
            }
        }

        return -1; // Element not found
    }

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

        int result = binarySearchRecursive(arr, target, 0, arr.length - 1);

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

Output:

Element found at index 4

Time Complexity: O(log n) where n is the size of the given array. 

Space Complexity: O(log n) because extra stack space is required to perform Recursion.

Java Program for Binary Search Using Built-in Function.

In Java, you can use the Arrays.binarySearch() method to perform a binary search on an array. This method is part of the java.util package and is designed to work with arrays that are already sorted.

Java Code:

// Binary Search Built-in Function in Java to search 
// an element in sorted array
import java.util.Arrays;

public class BinarySearch {

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

        // Sorting the array (required for binary search)
        Arrays.sort(arr);

        // Using binarySearch method
        int result = Arrays.binarySearch(arr, target);

        if (result >= 0) {
            System.out.println("Element found at index " + result);
        } else {
            System.out.println("Element not found in the array");
        }
    }
}

Output:

Element found at index 5

Time Complexity: The Arrays.binarySearch() method has a time complexity of O(log n), similar to a standard binary search algorithm.

Space Complexity: The Arrays.binarySearch() method has a space complexity of O(1). It doesn't require additional memory that scales with the size of the input.