How to use recursion in Java's binary search algorithm?

1. Recursive concept

The programming technique in which a program calls itself is called recursion. Turn large-scale problems into small-scale problems. The problem remains the same and the scale becomes smaller.

2. Two prerequisites

Termination condition - when certain conditions are met, the function returns a specific value and no longer calls recursively

Recursive call ——The function calls itself, and its input value is closer to the termination condition

3. Recursive example of binary search

/**
     * 递归实现二分查找
     * @param arr
     * @param left
     * @param right
     * @param val
     * @return
     */
private static int binarySearch(int[] arr, int left, int right, int val) {
        if (val < arr[left] || val > arr[right] || left > right) {
            return -1;
        }
        int middle = (left + right)/2;
        if(val < arr[middle]){
            return binarySearch (arr,0,middle-1,val);
        }
        if(val > arr[middle]){
            return binarySearch (arr,middle+1,right,val);
        }else{
            return middle;
        }
}

The above is the detailed content of How to use recursion in Java's binary search algorithm?. For more information, please follow other related articles on the PHP Chinese website!