二分查找递归解法

额 我感觉不需要说什么的,递归本就需要点想象吧~

package 递归基础小题;

import java.util.Scanner;

/**
 * @author 邓雪松 (づ ̄ 3 ̄)づ)
 * @create 2021-10-25-19-06
 */
public class 二分查找递归解法 {
    public static void main(String[] args) {
        int arr[] = {1,3,2,4,5,6,8};
        System.out.println("请输入你想查找的整数(1-10):");
        Scanner scanner = new Scanner(System.in);
        int x = scanner.nextInt();
        int y = binarySearch1(arr,0,arr.length,x);
        if(y==-1){
            System.out.println("查无此数~");
        }else{
            System.out.println("查有此数~");
        }
    }

    //递归解法
    private static int binarySearch1(int[] arr,int low,int high,int key){
        if(low>high)
            return -1;//没找到
        int mid = low + ((high-low)>>1);//(low+high)>>>1;//防止溢出,移位也更高效
        int midVal = arr[mid];
        if(midVal<key)
            return binarySearch1(arr,mid+1,high,key);
        else if(midVal>key)
            return binarySearch1(arr,low,high-1,key);
        else
            return mid;//key found
    }
}

运行结果如下

请输入你想查找的整数(1-10):
7
查无此数~
上一篇:算法设计与分析——分治DC算法


下一篇:两数之和 II - 输入有序数组