xinyi_java 2021-09-12 14:16 采纳率: 100%
浏览 33
已结题

如果要查找的key是数组中最后一个元素设置最大下标的时候就不能用(数组长度-1)了【不查找最后一个的话都是正常的】

package bi.shi.demo01;

import org.junit.Test;

/**
 * @program: bi_shi_test
 * @description: 写一个折半查找算法
 * 搜索过程从数组的中间元素开始,
 * 如果中间元素正好是要查找的元素,
 * 则搜索过程结束;
 * 如果某一特定元素大于或者小于中间元素,
 * 则在数组大于或小于中间元素的那一半中查找,
 * 而且跟开始一样从中间元素开始比较。
 * 如果在某一步骤数组为空,
 * 则代表找不到。
 * 这种搜索算法每一次比较都使搜索范围缩小一半
 * @author: xin yi
 * @create: 2021-09-12 13:42
 */
public class Demo01 {
    /**
     * ① 首先确定整个查找区间的中间位置 mid = (left + right)/2 。
     * ② 用待查关键字值与中间位置的关键字值进行比较;若相等,则查找成功;若大于,则在后(右)半个区域继续进行折半查找;若小于,则在前(左)半个区域继续进行折半查找。
     * ③ 对确定的缩小区域再按折半公式,重复上述步骤。最后,得到结果:要么查找成功, 要么查找失败。折半查找的存储结构采用一维数组存放.
     */
    @Test
    public void demo01(){
        int arr[] =new int[]{2,4,6,8,10,12,14,16,18,20,22};
        System.out.println(zhebanFind(arr, 2));
        System.out.println(zhebanFind(arr, 4));
        System.out.println(zhebanFind(arr, 6));
        System.out.println(zhebanFind(arr, 8));
        System.out.println(zhebanFind(arr, 10));
        System.out.println(zhebanFind(arr, 12));
        System.out.println(zhebanFind(arr, 14));
        System.out.println(zhebanFind(arr, 16));
        System.out.println(zhebanFind(arr, 18));
        System.out.println(zhebanFind(arr, 20));
        System.out.println(zhebanFind(arr, 22));

    }

    private int zhebanFind(int[] arr, int key) {
        int maxArr = arr.length-1; /*设置最大下标*/
        int minArr = 0; /*设置最小下标*/
        int midArr = (maxArr + minArr)/2; /*设置中间下标*/
        for (int i = 0; i < arr.length; i++) {
            if (arr[midArr] > key){ /*数组中间下标值比key大时,说明key在数组的前半段*/
                maxArr = midArr; /*重新设置最大下标*/
                midArr = midArr/2; /*重新设置最小下标*/
            }else if (arr[midArr] < key){ /*数组中间下标值比key小时,说明key在数组的后半段*/
                minArr = midArr; /*重新设置最小下标*/
                midArr = (minArr + maxArr)/2; /*重新设置最大下标*/
            }else {
                break;
            }
        }
        return midArr;
    }

}


这是length没-1的

img

  • 写回答

1条回答 默认 最新

  • Pliosauroidea 2021-09-12 14:36
    关注

    折半查找的mid一开始是4,然后变为(4+9)/2=6,然后变为7,8,但是(8+9)/2还是8,一直查不到9,所以会卡死
    有帮助望采纳

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 9月20日
  • 已采纳回答 9月12日
  • 修改了问题 9月12日
  • 创建了问题 9月12日

悬赏问题

  • ¥15 MATLAB yalmip 可转移负荷的简单建模出错,如何解决?
  • ¥15 数学的三元一次方程求解
  • ¥20 iqoo11 如何下载安装工程模式
  • ¥15 本题的答案是不是有问题
  • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?