`
teasp
  • 浏览: 61141 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

二分法查找第一个满足条件的项

阅读更多
public class BinSearch1st {
    Random random = new Random();
    
    /**
     * 二分查找,找到s的下标,如果没有返回-1
     * @param arr
     * @param s
     * @return
     */
    public int bsearch(int[] arr, int s) {
        int left = 0;
        int right = arr.length - 1;
        int cur = 0;
        
        while (left <= right) {
            cur = (left + right) >>> 1;
            if (arr[cur] > s) {                
                right = cur - 1;
            } else if (arr[cur] < s) {
                left = cur + 1;
            } else {
                return cur;
            }
        }
        
        return -1;
    }

    /**
     * 找到第一个s的下标,如果没有返回-1
     * @param arr
     * @param s
     * @return
     */
    public int search(int[] arr, int s) {
        int leftM = 0;
          
        int left = 0;
        int right = arr.length - 1;
        int cur = 0;
        
        while (left <= right) {
            cur = (left + right) >>> 1;
            if (arr[cur] > s) {                
                right = cur - 1;
            } else if (arr[cur] < s) {
                left = cur + 1;
                leftM = left;
            } else {
                if (arr[leftM] == arr[cur]) {//这个地方容易被忽略
                    return leftM;
                } else if (leftM < cur && arr[leftM] < arr[cur] && left < right) {
                    right = cur;
                } else {
                    return cur;
                }
            }
        }
        
        return -1;
    }
    
    @Test
    public void test() {
        int len = 10 + random.nextInt(100);
        int[] arr = new int[len];
        for (int i=0; i<len; i++) {
            arr[i] = random.nextInt(len);
        }
        Arrays.sort(arr);
        
        int s = arr[random.nextInt(len)];
        int i = search(arr, s);
        int j = 0;
        for (; j<len; j++) {
            if (arr[j] == s) {
                break;
            }
        }
        System.out.println(Arrays.toString(arr));
        System.out.println(i + " : " + arr[i] + " : " + s + " : " + j);
        Assert.assertEquals(j, i);
        int bs = bsearch(arr, s);
        Assert.assertEquals(s, arr[bs]);
        
        s = len;
        i = search(arr, s);
        bs = bsearch(arr, s);
        Assert.assertEquals(-1, i);
        Assert.assertEquals(-1, bs);
    }
    
    public static void main(String[] args) {
        BinSearch1st b = new BinSearch1st();
        for (int i=0; i<100; i++)
            b.test();
    }
}

 

0
5
分享到:
评论

相关推荐

    二分法程序

    - 寻找满足某个条件的第一个或最后一个位置。 - 求解函数的根(即求解方程`f(x) = 0`)。 #### 三、二分法的详细流程 ##### 3.1 初始化 - 定义初始搜索范围:`[xa, xb]`,其中`xa`为搜索区间的左端点,`xb`为右端...

    北大ACM、NOIP课程二分法

    这在处理类似查找第一个不大于给定值的位置等场景中非常有用。 二分法不仅可用于查找问题,还可以用来求解数值方程。例如,当需要找到一个单变量实函数的根时,如果已知函数在某个区间内单调,且函数值在区间端点处...

    C 二分法求方程根.rar

    5. **更新区间**: 根据第4步的判断结果,将原区间替换为新的子区间,重复步骤3到5,直到满足停止条件(比如达到预设的精度或迭代次数)。 在“VC 源码-算法相关”的标签下,我们可以期待在"codesc.net"这个文件中...

    算法竞赛专题解析--二分法三分法1

    C++标准库STL提供了`lower_bound()`和`upper_bound()`函数,它们分别返回大于等于目标值的第一个元素的迭代器和大于目标值的第一个元素的迭代器,适用于已排序的容器。 **2.3 简单例题** 二分法常常应用于解决如...

    新教材2020-2021学年高中数学第一册跟踪训练:4.5.2 用二分法求方程的近似解 含解析.doc

    例如题目中的第1题,因为B选项的零点两侧函数值同号,所以不适用二分法。 2. **精度ε与计算次数的关系**:第2题指出,ε越大,零点的精确度越低,因为ε是预设的误差范围,如果ε增大,意味着我们接受的误差范围也...

    二分法练习[参照].pdf

    6. **区间选择**:在第4题中,函数f(x) = 1/x - ln x在(1, 2)内有一个零点,每次等分区间后,当区间的长度小于0.1时,可以停止等分,因此需要将区间等分4次,因为2^(4-1) &gt; 0.1。 7. **二分法限制**:如第6题所示,...

    用二分法求方程的近似解247490PPT课件.pptx

    - 第一步:将电缆分成两部分,第1到第8个接点为一部分,第8到第15个接点为另一部分。 - 第二步:检测第一部分,如果故障不存在,则故障位于第二部分;如果故障存在,则故障位于第一部分。 - 第三步:重复上述过程...

    辽宁省沈阳市第二十一中学高中数学 2.4.2求函数零点近似解的一种计算方法 二分法课件 新人教A版必修1

    **二分法(对分法)求函数零点近似解**是高中数学中的一个重要概念,主要用于寻找实数解在给定区间内的方程。在实际应用中,如查找电线故障、确定通信线路问题等,这种方法能有效地缩小查找范围,提高效率。 二分法...

    山东省乐陵市第一中学2015高中数学 2.4.2 求函数零点近似解的一种计算方法 二分法合作探究 新人教A版必修1

    二分法,也称为折半查找法,是求解函数零点近似解的一种高效算法,尤其适用于已知函数在某区间内存在零点的情况。这种方法主要基于连续函数的介值定理,即如果函数在闭区间[a, b]上连续,且f(a) * f(b) ,那么在区间...

    2018年秋高中数学第三章函数的应用3.1函数与方程3.1.2用二分法求方程的近似解练习新人教A版必修120180818220

    例如,在第8题中,要找到一枚轻一些的假金币,通过二分法最多只需4次称量,每次都将待检测的金币数量减半,从而迅速定位到假币。 总的来说,二分法是一种高效且实用的数值方法,尤其适用于解决方程求解和查找问题,...

    计算机二级公共基础知识

    能使用二分法查找的线性表必须满足用顺序存储结构和线性表是有序表两个条件。 “有序”是特指元素按非递减排列,即从小到大排列,但允许相邻元素相等。下一节排序中,有序的含义也是如此。 对于长度为n的有序线性表...

    用二分法求方程的近似解47958PPT课件.pptx

    在实际问题中,例如找一枚较轻的金币,也可以利用类似二分法的思想来降低查找次数。 总结来说,二分法是通过不断将可能包含零点的区间减半,逐步逼近零点,从而找到方程的近似解。这种方法简单且有效,特别适合...

    二分入门PPT

    - `lower_bound`:返回容器中第一个不小于给定元素的元素的位置。 - `upper_bound`:返回容器中第一个大于给定元素的元素的位置。 - `pair&lt;&gt; equal_range`:返回一个范围,该范围内包含所有与给定元素相等的元素。 ...

    汉语词典快速查找算法研究.pdf

    编码后的词语被拆分为两段,第一段称为前缀码,第二段称为后缀码。在查询时,先通过前缀码快速定位到可能的词语区间,再通过后缀码进一步精确匹配,这样既减少了搜索范围,又保持了较高的查询精度。 #### 实验分析 ...

    苏教版必修三第1章 算法初步作业题及答案解析12套精选.docx

    5. 二分法:二分法是一种求解方程近似解的算法,适用于查找有序数组中的元素或求解连续函数的零点。在第2题中,使用二分法求解方程的近似根。 6. 变量交换:在算法中,有时需要交换两个变量的值,通常可以通过临时...

    2015高中数学3.1.2用二分法求方程的近似解课时跟踪检测新人教A版必修1

    7. **二分法查找最小值**:在第7题中,通过二分法查找假金币,每次可以将待查找范围减半,最多需要称量的次数与对数有关,但不超过log2(26) ≈ 4.7,实际操作中可能需要5次。 8. **函数零点的判断**:填空题第18题...

    算法导论笔记

    - 最简单的方法是从数组的第一个元素开始,逐个比较相邻元素来寻找峰值,这种方法的时间复杂度为 \(O(n)\)。 - 更高效的方法是使用二分法查找峰值,时间复杂度可以降低到 \(O(\log n)\)。 **具体步骤:** 1. 如果...

    宁夏银川市第九中学高中数学3.1.2用二分法求方程的近似解教案新人教A版必修1

    课后的练习和作业旨在巩固所学知识,包括教材中的练习题和作业题,如第106页练习1、2题及第108页第1题,以及第108页的第3、4、5、6题,这些题目会要求学生独立应用二分法解决方程求解问题。 总的来说,本节课的教学...

    高一数学第一学期普通高中教学质量监控试题.doc

    16. 查找表函数:第十六题中,给定一个函数的表格,需要找出满足特定条件的x值。 17. 三角函数化简:第十七题可能需要利用三角恒等式进行化简。 18. 集合的基本运算:解答题中的第一题涉及集合的补集和交集运算,...

    c语言 题 目 级答案

    【4.55】对称数的寻找可以通过检查数字的每一位是否等于倒数第二位,倒数第三位是否等于倒数第四位,最后一位等于第一位。对于二进制数,只需检查二进制位是否对称。 【4.56】解这个谜题需要用到代数方法,将等式...

Global site tag (gtag.js) - Google Analytics