Java 实现二分查找(在 1-100 里找到目标值)

前言:

二分查找(也是折半查找),是每次用目标值和一个有序数列的中间值对比。这样的话每次都可以抛弃一半,随之范围也会缩小一半。所以每一次都找中间值对比,范围也每次都缩小一半。直到对比出结果为止!

例子:

题目:

使用随机数产生一个目标值(范围1-100):在一个有序数列1-100的数组里找到目标值。
要求:循环次数不能超过10次

整体代码实现:

封装的方法

  //最多用10次猜测出,(1-100范围内)产生的随机数。
    public static String RandomGame(int randonNum){
        int[] array=new int[100];
        String str="";
        for (int i = 1; i <= 100; i++) {
            array[i-1]=i;
        }//循环向数组里存入100个数字
        int left=0;//开始位置
        int right=array.length-1;//结束位置
        for (int j = 0; j < 10; j++) {
            int mid=(left+right)/2;//中间位置索引
            //每次用目标值和中间值做对比
            //目标值大于中间值
            if (randonNum>array[mid]){
                //改变其实位置,起始位置等于mid+1,
                也就是从中间位置往右诺一位
                left=mid+1;
            }
            //目标值小于中间语句
            if(randonNum<array[mid]){
                right=mid-1;
            }
            //目标值等于中间语句
            if(randonNum==array[mid]){
                str="恭喜猜中了,目标值为"+array[mid]+
                "循环次数为"+j+"次";
                break;//出结果就结束循环
            }
        }
        return str;
    }

客户端:

        Random r=new Random();//产生随机数
        //正确答案
        int randomNum=r.nextInt(100)+1;//产生[1,100]的随机数
        System.out.println("目标值为:"+randomNum);
        //获取对比结果
        String  relust=RandomGame(randomNum);
        System.out.println(relust);//输出结果

实现结果

Java实现二分查找(在1-100里找到目标值)

实现分解:

1 定义目标值(使用随机函数生成目标值范围:1-100)

        Random r=new Random();//产生随机数
        //目标值
        int randomNum=r.nextInt(100)+1;//产生[1,100]的随机数

2 定义左边界索引

 int right=array.length-1;//结束位置

3 定义佑边界索引

 int right=array.length-1;//结束位置

4定义中间索引和循环对比(在循环里定义中间值索引或者循环外面,都行)
核心代码:(结合实现分解的2,3步骤)

for (int j = 0; j < 10; j++) {
            int mid=(left+right)/2;//中间位置索引
            //每次用目标值和中间值做对比
            //目标值大于中间值
            if (randonNum>array[mid]){
                //改变其实位置,起始位置等于mid+1,
                也就是从中间位置往右诺一位
                left=mid+1;
            }
            //目标值小于中间语句
            if(randonNum<array[mid]){
                right=mid-1;
            }
            //目标值等于中间语句
            if(randonNum==array[mid]){
                str="恭喜猜中了,目标值为"+array[mid]
                +"循环次数为"+j+"次";
                break;//出结果就结束循环
            }
        }
本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!