Java Binary Search

Binary search is an efficient algorithm for finding an element in a sorted array. It works by repeatedly dividing the search interval in half and comparing the element at the midpoint with the target element. If the target element is less than the element at the midpoint, the search continues in the lower half of the interval. If it is greater, the search continues in the upper half. The algorithm repeats this process until the target element is found or it is clear that the element is not present in the array.

To implement binary search in Java, you can use a recursive function that takes the following arguments:

• array: the sorted array to search
• target: the target element to search for
• low: the low index of the search interval
• high: the high index of the search interval

The function should return the index of the target element if it is found, or -1 if it is not found.

Here is an example of how to implement binary search in Java:

public class BinarySearch {

    public static int search(int[] array, int target, int low, int high) {
        if (low > high) {
            return -1;
        }
        int mid = low + (high - low) / 2;
        if (array[mid] == target) {
            return mid;
        } else if (target < array[mid]) {
            return search(array, target, low, mid - 1);
        } else {
            return search(array, target, mid + 1, high);
        }
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int target = 5;
        int index = search(array, target, 0, array.length - 1);
        if (index == -1) {
            System.out.println(target + " not found in array");
        } else {
            System.out.println(target + " found at index " + index);
        }
    }
}

In this example, the search() method is a recursive function that implements the binary search algorithm. The main() method searches for the element 5 in the array {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and prints the result.

To run the example, create a new Java class and copy the code into it. Run the class using the java command. The output should be:

5 found at index 4

You can also use an iterative approach to implement binary search in Java. The iterative approach is generally faster and uses less stack space, but it is less intuitive than the recursive approach.