Binary Search

Binary search is a widely used search algorithm that finds the position of a target value within a sorted array. It compares the target value to the middle element of the array and repeatedly divides the search interval in half to narrow down the search range.

The binary search algorithm can be implemented using recursion. Here's an example implementation in Java:

{{code}}

In this example, the binarySearch function takes an integer array arr and a target value target as input. It calls the recursive helper function binarySearch with additional parameters start and end, initially set to the first and last indices of the array.

The base case of the recursion is when start becomes greater than end, indicating that the target value is not found in the current search range. In this case, the function returns -1.

In the recursive case, the function calculates the middle index (mid) of the current search range and compares the value at arr[mid] with the target value. If they are equal, the function returns the index mid. If the target value is less than arr[mid], the function makes a recursive call to search the left half of the array (start remains the same, end becomes mid - 1). If the target value is greater than arr[mid], the function makes a recursive call to search the right half of the array (start becomes mid + 1, end remains the same).

Try running the example code to see binary search in action. It searches for the value 5 in the sorted array [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and prints the index at which it is found.

xxxxxxxxxx

}

public class BinarySearch {

​

  public static int binarySearch(int[] arr, int target) {

    return binarySearch(arr, target, 0, arr.length - 1);

  }

​

  private static int binarySearch(int[] arr, int target, int start, int end) {

    if (start > end) {

      return -1;

    }

​

    int mid = start + (end - start) / 2;

​

    if (arr[mid] == target) {

      return mid;

    } else if (arr[mid] < target) {

      return binarySearch(arr, target, mid + 1, end);

    } else {

      return binarySearch(arr, target, start, mid - 1);

    }

  }

​

  public static void main(String[] args) {

    int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    int target = 5;

    int index = binarySearch(arr, target);

    System.out.println("Target " + target + " found at index: " + index);

  }

​